84
правки
Изменения
м
→Теорема Фринка (Frink)
Пусть <tex>G = (V, E)</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>) сохранит двусвязность графа.
