49
правок
Изменения
→Формула Бержа
|proof=
Удалим из графа <tex>G</tex> множество <tex>S</tex>, получим <tex>t</tex> компонент связности, содержащих <tex>k_1, k_2 ... k_t</tex> вершин соответственно.
<tex>|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n\; </tex> , т. к . в сумме это все вершины исходного графа <tex>G</tex>.
Возьмем данное равенство по модулю два: <tex>(|S|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = n \; mod \; 2</tex>
В сумме <tex>\sum_{i=1}^{k}(k_i \; mod \; 2)</tex> число единиц равно числу нечетных компонент <tex>odd(G \setminus S)</tex>. Таким образом, <tex> \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 \; = \; n \; mod \; 2 \; </tex>.
}}
