497
правок
Изменения
Нет описания правки
откуда немедленно следует доказываемое утверждение.
}}
[[Файл: Grinberg_Graph.png|300px|thumb|right|Граф Гринберга]]
Используя свою теорему, Гринберг построил трёхсвязный кубический плоский граф, в котором ровно одна грань имеет <tex>9</tex> рёбер, а все остальные {{---}} по <tex>5</tex> или <tex>8</tex> рёбер.
Левая часть соотношения <math>\sum_{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|Граф Гринберга. Проставлено количество ребер в гранях.]]
Придуманый Гринбергом в 1968 году критерий негамильтоновисти графа, позволил наконец построить контрпримеры к [http://en.wikipedia.org/wiki/Tait%27s_conjecture|гипотизе Тейта](1884г) о том, что любой 3-регулярный трёхсвязный планарный граф имеет гамильтонов цикл. Долгое время единственным контрпримером к этой гипотезе был [http://en.wikipedia.org/wiki/Tutte_graph| граф Татта](1946), негамильтоновость которого доказывалась перебором.
