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 and graduate students Dawei He and Yan Wang.[1]
References
- ^ a b Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |