Przypuszczenie Kelmansa-Seymoura
W teorii grafów hipoteza Kelmansa -Seymoura mówi, że każdy graf połączony z 5 wierzchołkami , który nie jest planarny , zawiera podpodział pełnego grafu z 5 wierzchołkami K 5 . Jej nazwa pochodzi od Paula Seymoura i Alexandra Kelmansa, którzy niezależnie opisali przypuszczenie; Seymour w 1977 i Kelmans w 1979. Dowód ogłoszono w 2016 i opublikowano w czterech artykułach w 2020.
Sformułowanie
Graf jest spójny w 5 wierzchołkach, gdy nie ma pięciu wierzchołków, które po usunięciu pozostawiają graf rozłączony. Pełny graf to graf z krawędzią między każdymi pięcioma wierzchołkami, a podział pełnego grafu modyfikuje to, zastępując niektóre jego krawędzie dłuższymi ścieżkami. Tak więc graf G zawiera podpodział K 5 , jeśli możliwe jest wybranie pięciu wierzchołków G oraz zbiór dziesięciu ścieżek łączących te pięć wierzchołków parami, przy czym żadna ze ścieżek nie ma wspólnych wierzchołków ani krawędzi.
Na dowolnym rysunku grafu na płaszczyźnie euklidesowej co najmniej dwie z dziesięciu ścieżek muszą się przecinać, więc graf G zawierający podpodział K 5 nie może być grafem planarnym . Z drugiej strony, zgodnie z twierdzeniem Kuratowskiego , graf, który nie jest planarny, koniecznie zawiera podpodział albo K 5 , albo pełnego dwudzielnego grafu K 3,3 . Hipoteza Kelmansa-Seymoura udoskonala to twierdzenie, podając warunek, w którym można zagwarantować istnienie tylko jednego z tych dwóch podpodziałów, podpodziału K 5 . Stwierdza, że jeśli graf niepłaski jest spójny w 5 wierzchołkach, to zawiera on podpodział K 5 .
Powiązane wyniki
Powiązany wynik, twierdzenie Wagnera , stwierdza, że każdy graf niepłaski połączony z 4 wierzchołkami zawiera kopię K 5 jako graf mniejszy . K5 Jednym ze sposobów przekształcenia tego wyniku jest to, że na tych grafach zawsze można wykonać sekwencję operacji skracania krawędzi , tak aby wynikowy graf zawierał podpodział . Przypuszczenie Kelmansa-Seymoura stwierdza, że przy łączności wyższego rzędu skurcze te nie są wymagane.
Wcześniejsza hipoteza Gabriela Andrew Diraca (1964), udowodniona w 2001 roku przez Wolfganga Madera, stwierdza, że każdy n -wierzchołkowy graf z co najmniej 3 n -5 krawędziami zawiera podpodział K 5 . Ponieważ grafy planarne mają co najwyżej 3 n -6 krawędzi, grafy z co najmniej 3 n -5 krawędziami muszą być niepłaskie. Jednak nie muszą być 5-połączone, a grafy 5-połączone mogą mieć zaledwie 2,5 n krawędzi.
Domniemany dowód
Georgia Institute of Technology i jego doktorant zażądali dowodu na hipotezę Kelmansa-Seymoura. studenci Dawei He i Yan Wang. Sekwencja czterech artykułów potwierdzających to przypuszczenie ukazała się w Journal of Combinatorial Theory, Series B.