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>.
тогда <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>, что и требовалось доказать.
}}
==Теорема Петерсона (Petersen)==
{{Определение
|id=th1.
|author=Петерсон
|statement=Кубический Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, у которого нет в котором не более <tex>3</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенного паросочетаниясовершенное паросочетание]], содержит как минимум <tex>3</tex> моста. |proof = }}
Следствие из данной теоремы: для любого [[Отношение связности, компоненты связности| двусвязного]] кубического графа существует совершенное паросочетание.
