Re: Vertex coloring
- From: jankrihau@xxxxxxxxxxx
- Date: 30 Apr 2007 12:43:13 -0700
On 30 Apr, 21:07, tgt1...@xxxxxxxxx wrote:
Hi everyone,
I am trying to prove a theorem about the relationship between the
vertex colouring number (chromatic number) of a graph and the minimum
number of edges in that graph. My book states that: if the chromatic
number of a graph is n, the number of edges in that graph must be at
least 2n. I am not entirely sure how to approach it. They give the
specific example of a 5-colourable graph which must have at least 10
edges, but that doesn't explain it at all.
Any help at all would be great!
Thanks
I think the minimal number of edges should be C(n, 2) = (n^2 - n) / 2.
Incidentally, this equals 10 for n = 5.
---
J K Haugland
http://home.no.net/zamunda
.
- Follow-Ups:
- Re: Vertex coloring
- From: tgt1979
- Re: Vertex coloring
- References:
- Vertex coloring
- From: tgt1979
- Vertex coloring
- Prev by Date: Re: f(x) = 1/x: to be or not to be continuous ...
- Next by Date: Re: I don't like the Axiom of Choice
- Previous by thread: Vertex coloring
- Next by thread: Re: Vertex coloring
- Index(es):
Relevant Pages
|
|
