Kelmans–Seymour conjecture
In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979.[1]
By Kuratowski's theorem, a nonplanar graph necessarily contains a subdivision of either K5 or the complete bipartite graph K3,3. The conjecture refines this by providing a condition under which one of these two graphs can be guaranteed to exist. In this sense, it is the analogue for topological minors of Wagner's theorem that 4-connected nonplanar graphs contain K5 as a graph minor.
In 2016, a proof was claimed by Xingxing Yu, Georgia Tech mathematics professor and his Ph.D. students Dawei He and Yan Wang.[2][3]
Precise formulation of the theorem
Every 5-connected nonplanar graph contains a subdivision of K5.
See also
References
- ↑ Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos.
- ↑ He, Dawei; Wang, Yan; Yu, Xingxing (2015-11-16). "The Kelmans-Seymour conjecture I: special separations". arXiv:1511.05020 [math.CO].
- ↑ He, Dawei; Wang, Yan; Yu, Xingxing (2016-02-24). "The Kelmans-Seymour conjecture II: 2-vertices in $K_4^-$". arXiv:1602.07557 [math.CO].