Harvard-MIT Math Tournament

Solution:

The minimum number of edges is $\frac{n(n-1)}{2}$.

We prove this claim by induction. It holds for $n=1$.

Now assume the claim holds for $n$, and consider a graph of chromatic number $n+1$. This graph must have at least one vertex of degree $n$, or else, by part a), it could be colored with only $n$ colors.

Now, if we remove this vertex, the remaining graph must have chromatic number $n$ or $n+1$—if the chromatic number is $n-1$ or less, we can add the vertex back and give it a new color, creating a good coloring with only $n$ colors. By the inductive hypothesis, the new graph has at least $\frac{n(n-1)}{2}$ edges, so the original graph had at least $\frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$ edges.

The complete graph on $n+1$ vertices has exactly $\frac{n(n+1)}{2}$ edges, so the lower bound is tight and the inductive step is complete.