Kelmans–Seymour conjecture

Template:Math subdivision of the 12-vertex crown graph

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 Template:Math. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof was announced in 2016, and published in four papers in 2020.

Formulation

A graph is 5-vertex-connected when there are no five vertices that removed leave a disconnected graph. The complete graph is a graph with an edge between every five vertices, and a subdivision of a complete graph modifies this by replacing some of its edges by longer paths. So a graph Template:Mvar contains a subdivision of Template:Math if it is possible to pick out five vertices of Template:Mvar, and a set of ten paths connecting these five vertices in pairs without any of the paths sharing vertices or edges with each other.

In any drawing of the graph on the Euclidean plane, at least two of the ten paths must cross each other, so a graph G that contains a K₅ subdivision cannot be a planar graph. In the other direction, by Kuratowski's theorem, a graph that is not planar necessarily contains a subdivision of either Template:Math or of the complete bipartite graph Template:Math. The Kelmans–Seymour conjecture refines this theorem by providing a condition under which only one of these two subdivisions, the subdivision of Template:Math, can be guaranteed to exist. It states that, if a non-planar graph is 5-vertex-connected, then it contains a subdivision of Template:Math.

Related results

A related result, Wagner's theorem, states that every 4-vertex-connected nonplanar graph contains a copy of Template:Math as a graph minor. One way of restating this result is that, in these graphs, it is always possible to perform a sequence of edge contraction operations so that the resulting graph contains a Template:Math subdivision. The Kelmans–Seymour conjecture states that, with a higher order of connectivity, these contractions are not required.

An earlier conjecture of Gabriel Andrew Dirac (1964), proven in 2001 by Wolfgang Mader, states that every Template:Mvar-vertex graph with at least Template:Math edges contains a subdivision of Template:Math. Because planar graphs have at most Template:Math edges, the graphs with at least Template:Math edges must be nonplanar. However, they need not be 5-connected, and 5-connected graphs can have as few as Template:Math edges.

Claimed proof

In 2016, a proof of the Kelmans–Seymour conjecture was claimed by Xingxing Yu of the Georgia Institute of Technology and his Ph.D. students Dawei He and Yan Wang. A sequence four papers proving this conjecture appeared in Journal of Combinatorial Theory, Series B.

See also

• Four-color theorem
• Hajós' conjecture