84
правки
Изменения
м
→Теорема Фринка (Frink)
|statement=
Пусть <tex>G =(V, E) </tex> {{---}} </tex> двусвязный кубический граф.
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежены с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>, рисунок <tex>2</tex>) сохранит двусвязность графа.
