Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.
Solution 1:
Given a coloring of $G$ with $\chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.
Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.
Solution 1:
Given a coloring of $G$ with $\chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.