1. ## graph vertex colouring

Show that any graph can be properly vertex-colored with (2m)^(1/2) colors, where m is the number of edges.

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

3. thanks. That solves it.