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][2] A proof has been announced but not yet published.[1][3]
Formulation
A graph is 5-vertex-connected when there are no five vertices whose removal leaves 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 G contains a subdivision of K5 if it is possible to pick out five vertices of G, 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 K5 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 K5 or of the complete bipartite graph K3,3. The Kelmans–Seymour conjecture refines this theorem by providing a condition under which only one of these two subdivisions, the subdivision of K5, can be guaranteed to exist. It states that, if a non-planar graph is 5-vertex-connected, then it contains a subdivision of K5.
Related results
A related result, Wagner's theorem, states that every 4-vertex-connected nonplanar graph contains a copy of K5 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 K5 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 n-vertex graph with at least 3n − 5 edges contains a subdivision of K5. Because planar graphs have at most 3n − 6 edges, the graphs with at least 3n − 5 edges must be nonplanar. However, they need not be 5-connected, and 5-connected graphs can have as few as 2.5n edges.[4][5][6]
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.[3] A sequence four papers proving this conjecture appeared in Journal of Combinatorial Theory Series B.[7][8][9][10]
See also
Four-color theorem
Hajós' conjecture
References
Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos.
Note however that Thomassen (1997) dates Seymour's formulation of the conjecture to 1984.
He, Dawei; Wang, Yan; Yu, Xingxing (November 16, 2015), The Kelmans–Seymour conjecture I: special separations, arXiv:1511.05020; ——; et al. (February 24, 2016), The Kelmans–Seymour conjecture II: 2-vertices in \( {\displaystyle K_{4}^{-}} \), arXiv:1602.07557; ——; et al. (September 19, 2016), The Kelmans–Seymour conjecture III: 3-vertices in \( {\displaystyle K_{4}^{-}} \), arXiv:1609.05747; ——; et al. (December 21, 2016), The Kelmans–Seymour conjecture IV: A proof, arXiv:1612.07189
Dirac, G. A. (1964), "Homomorphism theorems for graphs", Mathematische Annalen, 153: 69–80, doi:10.1007/BF01361708, MR 0160203
Thomassen, Carsten (1997), "Dirac's conjecture on \( K_{5} \)-subdivisions", Discrete Mathematics, 165/166: 607–608, doi:10.1016/S0012-365X(96)00206-3, MR 1439305
Mader, W. (1998), " \( {\displaystyle 3n-5} \) edges do force a subdivision of \( K_{5} \)", Combinatorica, 18 (4): 569–595, doi:10.1007/s004930050041, MR 1722261
He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-11). "The Kelmans-Seymour conjecture I: Special separations". Journal of Combinatorial Theory, Series B. arXiv:1511.05020. doi:10.1016/j.jctb.2019.11.008. ISSN 0095-8956.
He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-11). "The Kelmans-Seymour conjecture II: 2-Vertices in K4−". Journal of Combinatorial Theory, Series B. arXiv:1602.07557. doi:10.1016/j.jctb.2019.11.007. ISSN 0095-8956.
He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-09). "The Kelmans-Seymour conjecture III: 3-vertices in K4−". Journal of Combinatorial Theory, Series B. arXiv:1609.05747. doi:10.1016/j.jctb.2019.11.006. ISSN 0095-8956.
He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-19). "The Kelmans-Seymour conjecture IV: A proof". Journal of Combinatorial Theory, Series B. arXiv:1612.07189. doi:10.1016/j.jctb.2019.12.002. ISSN 0095-8956.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
