Graph Theory (Edges and coloring)

Question

Show that $e(G) ≥ \binom{χ(G)}{2}$ for every graph G.

Here, $e(G)$ represents the number of edges in the graph.

Answer 1

Color $G$ using $\chi_G$ colors. For each pair of colors used (say, blue and red), there must be some edge connecting a red vertex to a blue one. If not, then recoloring all red vertices blue would result in a valid coloring with $\chi_G-1$ colors, contradicting the definition of $\chi_G$. Thus, for each pair of colors, we get a distinct edge in $G$, showing that the number of edges is at least $\binom{\chi_G}2$.