8
$\begingroup$

I have not been able to find a proof to the statement that if a graph $G$ has $\chi(G)=k$, then it must have at least $\binom{k}{2}$ edges. Would you be able to show me a simple proof?

1 Answers 1

16

Suppose we have a $k$-coloring of our graph, with $\chi(G)=k$. Then for any two colors, call them red and blue, there must be some edge that connects them; if there weren't, we could paint every red vertex blue, and we would have a $(k-1)$-coloring of our graph. There are $\binom{k}{2}$ pairs of colors, and any given edge cannot connect more than $2$ colors, so there must be at least $\binom{k}{2}$ edges in our graph.