78
правок
Изменения
м
→Теорема Гринберга
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер:
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. </center>
Посчитаем <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} </tex>, то есть количество всех исходящих ребер из <tex>X</tex>. По [[Лемма_о_рукопожатиях | лемме о рукопожатиях]] внутри <tex>X</tex> их будет <tex>2|E(X)|</tex>, но мы не посчитали ребра прикрепленные и к <tex>X</tex>, и к <tex>Y</tex>. Количество таких ребер , по определению бонда {{- --}} количество ребер в бонде <tex>H</tex>, то есть <tex>|E(H)|</tex>. Отсюда:
<center> <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex>. </center>
Поэтому:
