497
правок
Изменения
Нет описания правки
Пусть <tex>G</tex> плоский граф без петель с гамильтоновым циклом <tex>C</tex>, который делит плоскости на две области <tex>R</tex> и <tex>R'</tex>. Пусть <tex>k_i</tex> и <tex>k'_i</tex> {{---}} количества граней размера <tex>i</tex> в <tex>R</tex> и <tex>R'</tex> соответственно. Тогда
<math>\sum_sum\limits_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0</math>
|proof=
[[Файл: HamiltonExampleR.png|300px|thumb|right|Пример. Рёбра из гамильтонова цикла выделены красным]]
Отметим, что в гамильтоновом графе <tex>G</tex>, очевидно, нет [[Мост, эквивалентные определения|мостов]] и граница любой грани {{---}} простой цикл. Поэтому размер границы каждой его грани не более <tex>V(G)</tex>. Пусть <tex>e</tex> и <tex>e'</tex> {{---}} количества рёбер графа <tex>G</tex>, лежащих внутри областей <tex>R</tex> и <tex>R'</tex> соответственно. Так как <tex>C</tex> {{---}} гамильтонов цикл графа <tex>G</tex>, то область <tex>R </tex> разбита на <tex>e + 1</tex> граней. а область <tex>R'</tex> {{---}} на <tex>e' + 1</tex> граней. Получаем соотношения:
(1) <math>\sum_sum\limits_{i=3}^{V(G)}k_i=e+1</math>, <math>\sum_sum\limits_{i=3}^{V(G)}k'_i=e'+1</math>
Каждое внутреннее ребро области <tex>R</tex> входит в границы двух внутренних граней области <tex>R</tex>, а каждое ребро цикла <tex>C</tex> {{---}} в границу одной внутренней грани этой области. Аналогичное соотношение верно и для <tex>R'</tex>. Следовательно,
(2) <math>\sum_sum\limits_{i=3}^{V(G)}i*k_i=2e+E(C)</math>, <math>\sum_sum\limits_{i=3}^{V(G)}i*k'_i=2e'+E(C)</math>
Из соотношений (1) и (2) получаем:
<math>\sum_sum\limits_{i=3}^{V(G)}i(k_i-k'_i)=2(e - e')=\sum_sum\limits_{i=3}^{V(G)}2(k_i-k'_i)</math>
откуда немедленно следует доказываемое утверждение.
Используя свою теорему, Гринберг построил трёхсвязный кубический плоский граф, в котором ровно одна грань имеет <tex>9</tex> рёбер, а все остальные {{---}} по <tex>5</tex> или <tex>8</tex> рёбер.
Левая часть соотношения <math>\sum_sum\limits_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0</math> в таком графе, очевидно, не делится на <tex>3</tex>, так как сравнима по модулю <tex>3</tex> с <tex>(9 - 2)(k_9 − k'_9) = 7</tex>.
[[Файл: Grinberg_Graph_numbers.png|300px|thumb|left|Граф Гринберга. Проставлено количество ребер в гранях.]]
