Изменения

Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \geqslant \left\{ [ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}]</tex>.

В качестве доказательства воспользуемся теоремой Рингеля и Янгса о минимальном роде поверхности, на которую можно уложить граф <tex>K_p</tex>, а именно <tex>n = \gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left\{ [ \dfrac{7 + \sqrt{1 + 48n}}{2} \right\}]</tex>.

Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> <tex>{{---</tex> }} триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> <tex>{{---</tex> }} среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:

<tex>dV = 2E = 3F</tex>.

Воспользуемся следующей [[формула Эйлера | формулой Эйлера]] <tex>V - E + F = 2 - 2 n</tex>, откуда

<tex>E = V - E + F = + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n- 1)</tex>

Откуда <tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex> и подставляя в первое равенство получаем

Поскольку <tex>d \leqslant V - 1</tex>, то получаем, что

<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>.

Найдя Найдём единственный положительный корень неравенства получаем

Обозначим за <tex>H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Если <tex> V \leqslant H(n)</tex>, то тогда граф <tex>G</tex> очевидно можно раскрасить в <tex>H(n)</tex> цветов и неравенство верное. Допустим, что <tex>V > H(n)</tex>, тогда

Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, иначе если <tex>V - 1 > H(n)</tex>, то опять найдём вершину степени <tex>H(n) - 2</tex> и снова повторим наш алгоритмстянем её и будем продолжать так до тех пор, пока не получим желаемый граф.

Заметим, что теорема Хивуда не работает при <tex>n = 0</tex>, поэтому [[проблема четырёх красок]] не может быть доказана с помощью этой теоремы, однако при подстановке <tex>n = 0</tex> получаем, что <tex>\chi \left( S_0 \right) = 4</tex>.

* Ф.Харари «Теория графов» {{---}} М.: Мир, 1973 г. {{--- Теория графов (}} стр. 162 - 164)