Теорема Гринберга
Теорема Гринберга(англ. Grinberg) - необходимое условие содержания гамильтонова цикла планарным графом.
| Теорема (Гринберга): |
Пусть плоский граф без петель с гамильтоновым циклом , который делит плоскости на две области и . Пусть и — количества граней размера в и соответственно. Тогда
|
| Доказательство: |
|
Отметим, что в гамильтоновом графе , очевидно, нет мостов и граница любой грани — простой цикл. Поэтому размер границы каждой его грани не более . Пусть и — количества рёбер графа , лежащих внутри областей и соответственно. Так как — гамильтонов цикл графа , то область R разбита на граней. а область — на граней. Получаем соотношения: (1) , Каждое внутреннее ребро области входит в границы двух внутренних граней области , а каждое ребро цикла — в границу одной внутренней грани этой области. Аналогичное соотношение верно и для . Следовательно, (2) , Из соотношений (1) и (2) получаем: откуда немедленно следует доказываемое утверждение. |
Используя свою теорему, Гринберг построил трёхсвязный кубический плоский граф, в котором ровно одна грань имеет рёбер, а все остальные — по или рёбер. Левая часть соотношения в таком графе, очевидно, не делится на , так как сравнима по модулю с .
Придуманый Гринбергом в 1968 году критерий негамильтоновисти графа, позволил наконец построить контрпримеры к Тейта(1884г) о том, что любой 3-регулярный трёхсвязный планарный граф имеет гамильтонов цикл. Долгое время единственным контрпримером к этой гипотезе был граф Татта(1946), негамильтоновость которого доказывалась перебором.
