84
правки
Изменения
м
Нет описания правки
==Теорема Петерсона (Petersen)==
{{Определение
|id=cube_graf_def
|definition= '''Кубический граф''' (англ. ''Cubic graph'') граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным.}}
{{Теорема
|id=th1.
|author=Петерсон
|statement=[https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Кубический граф], у которого нет совершенного паросочетания, содержит как минимум <tex>3</tex> моста. }}
Следствие из данной теоремы: для любого двусвязного кубического графа существует совершенное паросочетание.
