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.
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.
Precise formulation of the theorem
Every 5-connected nonplanar graph contains a subdivision of K5.