1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Лемма о сравнимости по модулю 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 =
[[Файл:Сравнимость.png|300px|thumb|left|Иллюстрация к лемме]]
<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>.
{{Теорема
|id=th1.
|author=Петерсон
|statement = Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, в котором не более <tex>32</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof =
Предположим, что совершенного паросочетания в <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G)</tex>.
Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> есть совершенное паросочетание.
}}
[[Файл:Петерсен 3 моста.png|300px|thumb|left|Кубический граф с тремя мостами, в котором не существует совершенного паросочетания.]]
Заметим, что утверждение теоремы не может быть усилено до большего числа мостов, так как для случая с тремя мостами существует контрпример.
==Теорема Фринка (Frink)==
