edges and chromatic number inequality

Question

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?

Answer 1

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