Так как $\chi(G)=k$, то $G$ содержит подграф $H$ с $\chi(H)=k$ и числом вершин не более $k$ (критический подграф). В $H$ каждая вершина имеет степень не менее $k-1$, иначе её можно перекрасить, снизив хроматическое число. Сумма степеней не менее $k(k-1)$, значит $|E(H)| \geq k\frac{k-1}{2} = \binom{k}{2}$. Так как $H \subseteq G$, то $|E(G)| \geq \binom{k}{2}$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!