Let G be a simple graph with v vertices and every vertex of degree d. Show that

where is the chromatic number, the least k for which the graph G is k-colourable.

Printable View

- May 4th 2009, 05:35 AMJason Bournegraph theory, chromatic number relation
Let G be a simple graph with v vertices and every vertex of degree d. Show that

where is the chromatic number, the least k for which the graph G is k-colourable. - May 5th 2009, 04:26 AMNonCommAlg
__Remark__: let be the set of verices of if has this property that no two vertices in are adjacent, then this is because if then and so

a vertex in can be adjacent to at most vertices, which contradicts regularity of

now label the colors with and for any let be the set of all vertices in colored then clearly and for any also by the above

remark for all therefore: Q.E.D. - May 6th 2009, 04:05 AMNonCommAlg
there's a lower bound for the chromatic number of any simple graph, which generalizes your problem and the proof is just a simple modification of the proof i gave you:

let be any simple graph, the set of vertices of and the largest subset of with this property that no two vertices in are adjacent. then: