A matematika, azon belül a gráfelmélet területén a Kelmans–Seymour-sejtés kimondja, hogy bármely 5-szörösen összefüggő gráf, ami nem rajzolható síkba, tartalmazza homeomorf részgráfként a K5 5 csúcsú teljes gráfot. A sejtés nevét Paul Seymour és Alexander Kelmans matematikusokról kapta, akik egymástól függetlenül megfogalmazták – Seymour 1977-ben, Kelmans 1979-ben.[1]
A Kuratowski-tétel szerint egy síkba nem rajzolható gráf szükségképpen tartalmazza homeomorf részgráfként vagy a K5 teljes gráfot, vagy a K3,3 teljes páros gráfot. A Kelmans–Seymour-sejtés pontosítja ezt egy olyan feltétel megadásával, ami garantálja a két gráf közül az egyik létezését. Ebben az értelemben a Wagner-tétel topologikus minor-analógiája; a Wagner-tétel kimondja, hogy a 4-szeresen összefüggő síkba nem rajzolható gráfok tartalmazzák K5-t gráfminorként..
2016-ban a Georgia Tech matematikaprofesszora, Xingxing Yu és két PhD hallgatója, Dawei He és Yan Wang bejelentették a sejtés bizonyítását. Bizonyításuk online hozzáférhető.[2][3]
A tétel precíz megfogalmazása
Minden 5-szörösen összefüggő nem síkbarajzolható gráf tartalmazza homeomorf részgráfként a K5 teljes gráfot.
Kapcsolódó szócikkek
Jegyzetek