137
правок
Изменения
→Лемма о сравнимости по модулю 2
Пусть <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>.
тогда <tex>m = k|U| - 2e(G(U))</tex>. <tex>2e(G(U))</tex> чётно, поэтому <tex>m \equiv k|U| \pmod 2</tex>. Так как <tex> |U|</tex> нечётно, <tex>m \equiv k \pmod 2</tex>, что и требовалось доказать.
