Теорема Гринберга

Теорема Гринберга(англ. Grinberg) - необходимое условие содержания гамильтонова цикла планарным графом.

Теорема (Гринберга):

Пусть [math]G[/math] плоский граф без петель с гамильтоновым циклом [math]C[/math], который делит плоскости на две области [math]R[/math] и [math]R'[/math]. Пусть [math]k_i[/math] и [math]k'_i[/math] — количества граней размера [math]i[/math] в [math]R[/math] и [math]R'[/math] соответственно. Тогда [math]\sum_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0[/math]

Доказательство:

[math]\triangleright[/math]

Отметим, что в гамильтоновом графе [math]G[/math], очевидно, нет мостов и граница любой грани — простой цикл. Поэтому размер границы каждой его грани не более V(G). Пусть у и e' — количества рёбер графа G, лежащих внутри областей R и R' соответственно. Так как C — гамильтонов цикл графа G, то область R разбита на e + 1 граней. а область R' — на e' + 1 граней. Получаем соотношения: [math]\sum_{i=3}^{V(G)}k_i=e+1[/math] [math]\sum_{i=3}^{V(G)}k'_i=e'+1[/math]

[math]\triangleleft[/math]