Suppose that $|| ≤ ^2$ for some fixed $ ∈ N$. Prove that it is possible to assign a color to each vertex of so that at most 2 different colors are used in total and for each edge, its end vertices have different colors.
First, I need to consider a random coloring using only c colors but I am not sure how to continue..
Consider a random colouring using $c$ colours. For each edge, the probability that both vertices are the same colour is $1/c$. The expected number of monochromatic edges is then $\le c^2/c = c$. The probability that there are at most $c$ monochromatic edges is nonzero, so there exist colourings with $c$ colours that have at most $c$ monochromatic edges. Now take such a colouring, and using each of the remaining $c$ colours at most once, recolour one vertex of each monochromatic edge.