137
правок
Изменения
Нет описания правки
Из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем, что <tex>kn \leqslant k(|S| + 2) - 2</tex>, и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</tex> существует совершенное паросочетание.
}}
==Следствия==
Заметим, что [[Совершенное паросочетание в кубическом графе#th1 | Теорема Петерсона]] является следствием из этой теоремы, так как в графах Петерсена <tex>k = 3</tex>, <tex>\lambda(G) \leqslant 2 = k - 1</tex>, <tex>|V| чётно</tex> и <tex>|F| = 0 \leqslant k - 1</tex>
{{Утверждение
|id = statement2
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>. Тогда для любого ребра <tex>e \in E(G)</tex> существует совершенное паросочетание графа <tex>G</tex>, содержащее <tex>e</tex>.
|proof =
Пусть <tex>e = uv</tex>, а <tex>e_1 \cdots e_{k-1}</tex> {{---}} остальные рёбра, инцидентные вершине <tex>u</tex>. Согласно теореме, в графе <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex> есть совершенное паросочетание <tex>M</tex>. Так как <tex>u</tex> покрывается <tex>M</tex>, а <tex>e</tex> {{---}} единственное ребро <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex>, инцидентное <tex>u</tex>, <tex>u \in M</tex>
}}
==См. также==
