Изменения

|id=th1.

|statement=Кубический Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, у которого нет в котором не более <tex>2</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].| proof = Предположим, что совершенного паросочетанияв <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]]<tex>S \subset V(G)</tex>.  Пусть <tex>U_1, \ldots, U_n</tex> {{---}} все нечётные компоненты связности графа <tex>G \setminus S</tex>. <tex>m_i</tex> {{---}} количество ребёр <tex>G</tex>, связывающих вершины <tex>U_i</tex> с вершинами <tex>S</tex>.  По предыдущей лемме, все <tex>m_i</tex> нечётны. Так как не более чем два ребра графа <tex>G</tex> {{---}} мосты, содержит то не более, чем два числа из <tex>m_1, \ldots, m_n</tex> равны <tex>1</tex>, остальные числа не менее <tex>3</tex>. Так как минимум <tex>S</tex> {{---}} множество Татта, то <tex>odd(G \setminus S) > |S|</tex>. Так как количество вершин кубического графа <tex>G</tex> чётно, мы имеем <tex>S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2</tex>, следовательно, <tex>n = odd(G \setminus S) \geqslant |S| + 2</tex>. Тогда <tex>\sum\limits_{v \in S} d_G(v) \geqslant \sum\limits_{i = 1}^n m_i \geqslant 3n - 4 \geqslant 3(|S| + 2) - 4 = 3|S| + 2 >3|S| = \sum\limits_{v \in S} d_G(v)</tex>, что, очевидно, невозможно.  Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> мостаесть совершенное паросочетание. }}

Следствие из данной теоремы: для любого [[Отношение связностиФайл:Петерсен 3 моста.png|300px|thumb|left|Кубический граф с тремя мостами, компоненты связности| двусвязногов котором не существует совершенного паросочетания.]] кубического графа Заметим, что утверждение теоремы не может быть усилено до большего числа мостов, так как для случая с тремя мостами существует совершенное паросочетаниеконтрпример.