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>
Вычитаем дважды из формулы <tex>\textbf{(3)}</tex> формулу <tex>\textbf{(2)}</tex> и получаем:
