# Coloring a graph

I have a question about colorability of a graph.

Let $G$ be an undirected graph with $n > 3$ vertices and $m$ edges = $\{(i_1 < j_1), \ldots (i_m < j_m)\}.$ Prove that we can always color vertices in 3 colors such at least $\frac{2}{3} m$ edges don't connect vertices of the same color.

How should I start??

The graph is finite, right? So the number of $3$-colorings is finite. Choose a $3$-coloring which minimizes the number of "bad" edges (edges which join two vertices of the same color). Assume for a contradiction that more than $1/3$ of the edges are bad. Show that there is a vertex $v$ such that more than $1/3$ of the edges incident with $v$ are bad. Then show that $v$ can be recolored in such a way as to make the number of bad edges smaller, contradicting the assumption that it was already minimized.