Изменения
→Нижняя оценка количеством ребер и количеством вершин
{{Лемма
|about = нижняя оценка Геллера
|statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный связный неориентированный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами. Тогда, <texdpi=140>\frac{n^2}{n^2 - 2m} \leqslant \chi(G) </tex>.
|proof=
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>.
<texdpi=140>m \leqslant \frac{1}{2}n(n - 1) - \frac{1}{2}\sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1) \Rightarrow \frac{n^2}{n^2 - 2m} \leqslant \frac{n^2}{n^2 -n(n - 1) + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{n + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i| + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} = \frac{(\sum\limits^{\chi}_{i = 1}|V_i|)^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} \leqslant \chi</tex>.
}}
==Смотри так же==
*[[Хроматическое_число_планарного_графа|Хроматическое число планарного графа]]
