78
правок
Изменения
→Теорема Гринберга: - добавлены пояснения к доказательству теоремы
== Теорема Гринберга ==
{{Теорема
|aboutauthor=Гринберг
|statement=
Пусть связный граф <tex> G </tex> имеет гамильтонов бонд <tex> H </tex> с торцевыми графами <tex> X </tex> и <tex> Y </tex>. Пусть <tex> f_n^{X} </tex> и <tex> f_n^{Y} </tex> {{---}} число вершин в графов <tex> X </tex> и <tex> Y </tex> соответственно, имеющих в <tex> G </tex> степень <tex> n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) </tex>. Тогда:
<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) (f_n^{X} - f_n^{Y}) = 0 ~~~ \bf{(1)} </tex>. </center>
|proof=
Так как торцевые графы являются деревьями, токоличество их вершин на единицу больше количества ребер:
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. </center>
<center> <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex>. </center>
Поэтому:
<center> <tex> \textbf{(2)} - 2 \times \textbf{(3)} = \sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из '''<tex>\textbf{(4)'''}</tex>, приходим к '''<tex>\textbf{(1)'''}</tex>.
}}
