Teorema . Sea $G = (V,E)$ sea un gráfico simple con $n$ vértices, $m$ bordes y $\chi (G) = k$ . Entonces, $$m \geqslant {k \choose 2}$$
Intenté probarme a mí mismo, pero no hice ningún progreso. Soy consciente de la desigualdad $$n/ \alpha (G) \leqslant \chi (G) \leqslant \Delta(G) + 1,$$ donde $\Delta (G)$ es el grado máximo en $G$ y $\alpha (G)$ es el tamaño del conjunto máximo independiente de vértices del grafo. ¿Alguien tiene algún consejo? ( consejos se aprecian más que las respuestas completas)
