137
правок
Изменения
→Лемма о сравнимости по модулю 2
|id = lemma1.
|statement =
Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], <tex>U \in V(G)</tex>, <tex>|U|</tex> нечётно, <tex>m</tex>{{---}}число рёбер, соединяющих вершины множества <tex>U</tex> с вершинами из <tex>V(G) \setminus U</tex>. Тогда <tex>m \equiv k \pmod 2</tex>
|proof =
<tex>m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))</tex>, где <tex>e(G(U))</tex> - количество рёбер, соединяющих вершину из <tex>U</tex> с другой вершиной из <tex>U</tex>.
