Изменения

Перейти к: навигация, поиск
Лемма о сравнимости по модулю 2
<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>, что и требовалось доказать.
}}
137
правок

Навигация