Show that any graph can be properly vertex-colored with (2m)^(1/2) colors, where m is the number of edges.
Printable View
Show that any graph can be properly vertex-colored with (2m)^(1/2) colors, where m is the number of edges.
I assume you meant ceil(sqrt(2m)). (The theorem's false if you take the floor instead.)
The key lemma to prove first is that if G is colored optimally and c1 and c2 are two different colors, then there exists an edge between a vertex colored c1 and a vertex colored c2.
Now consider an optimal coloring of G. Let c be the number of colors used. Then by the lemma there is an edge in G for each of the c(c-1)/2 possible pairs of colors, and obviously each of these edges are distinct. Thus c(c-1)/2 <= m.
Manipulating this inequality gives
sqrt(2m) >= sqrt(c(c-1))
ceil(sqrt(2m)) >= ceil(sqrt(c(c-1))) = c, as desired.
thanks. That solves it.