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.
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.
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: