Kelmans-Seymour gissningar
I grafteorin säger Kelmans –Seymours gissningar att varje 5-vertex-ansluten graf som inte är plan innehåller en underavdelning av den 5-vertex kompletta grafen K 5 . Den är uppkallad efter Paul Seymour och Alexander Kelmans, som oberoende beskrev gissningen; Seymour 1977 och Kelmans 1979. Ett bevis tillkännagavs 2016 och publicerades i fyra tidningar 2020.
Formulering
En graf är 5-vertex-ansluten när det inte finns några fem hörn som tas bort lämnar en frånkopplad graf. Den fullständiga grafen är en graf med en kant mellan var femte hörn, och en underavdelning av en komplett graf modifierar detta genom att ersätta några av dess kanter med längre banor. Så en graf G innehåller en underavdelning av K 5 om det är möjligt att välja ut fem hörn av G , och en uppsättning av tio banor som förbinder dessa fem hörn i par utan att någon av banorna delar hörn eller kanter med varandra.
I varje ritning av grafen på det euklidiska planet måste minst två av de tio banorna korsa varandra, så en graf G som innehåller en K 5 -underavdelning kan inte vara en plan graf . I den andra riktningen, enligt Kuratowskis teorem , innehåller en graf som inte är plan nödvändigtvis en underavdelning av antingen K 5 eller av den fullständiga tvådelade grafen K 3,3 . Kelmans–Seymours gissningar förfinar denna teorem genom att tillhandahålla ett villkor under vilket endast en av dessa två underavdelningar, underavdelningen av K 5 , kan garanteras existera. Den anger att om en icke-plan graf är 5-vertex-ansluten, så innehåller den en underavdelning av K 5 .
Relaterade resultat
Ett relaterat resultat, Wagners teorem , säger att varje 4-vertex-ansluten icke-plan graf innehåller en kopia av K 5 som en graf minor . Ett sätt att omformulera detta resultat är att det i dessa grafer alltid är möjligt att utföra en sekvens av kantkontraktionsoperationer så att den resulterande grafen innehåller en K 5 -underavdelning. Kelmans–Seymour gissningen säger att med en högre ordning av anslutningar krävs inte dessa sammandragningar.
En tidigare gissning av Gabriel Andrew Dirac (1964), bevisad 2001 av Wolfgang Mader, säger att varje n -vertexgraf med minst 3 n − 5 kanter innehåller en underavdelning av K 5 . Eftersom plana grafer har högst 3 n − 6 kanter, måste graferna med minst 3 n − 5 kanter vara icke-plana. De behöver dock inte vara 5-kopplade, och 5-kopplade grafer kan ha så få som 2,5 n kanter.
Påstådda bevis
2016 hävdade Xingxing Yu från Georgia Institute of Technology och hans Ph.D. eleverna Dawei He och Yan Wang. En sekvens av fyra artiklar som bevisar denna gissning dök upp i Journal of Combinatorial Theory, Series B.