graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

. 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 contains a subdivision of if it is possible to pick out five vertices of , 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 graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

. In the other direction, by

Kuratowski's theorem In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subd ...

, a graph that is not planar necessarily contains a subdivision of either or of the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

. The Kelmans–Seymour conjecture refines this theorem by providing a condition under which only one of these two subdivisions, the subdivision of , can be guaranteed to exist. It states that, if a non-planar graph is 5-vertex-connected, then it contains a subdivision of .

Related results

A related result,

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on five ...

, states that every 4-vertex-connected nonplanar graph contains a copy of as a

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

. One way of restating this result is that, in these graphs, it is always possible to perform a sequence of

edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex ide ...

operations so that the resulting graph contains a 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 Gabriel Andrew Dirac (13 March 1925 – 20 July 1984) was a Hungarian/British mathematician who mainly worked in graph theory. He served as Erasmus Smith's Professor of Mathematics at Trinity College Dublin 1964-1966. In 1952, he gave a sufficie ...

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

Claimed proof

In 2016, a proof of the Kelmans–Seymour conjecture was claimed by Xingxing Yu of the

Georgia Institute of Technology The Georgia Institute of Technology, commonly referred to as Georgia Tech or, in the state of Georgia, as Tech or The Institute, is a public research university and institute of technology in Atlanta, Georgia. Established in 1885, it is part ...

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 The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...

''.

References

{{DEFAULTSORT:Kelmans-Seymour conjecture Planar graphs Graph minor theory

Formulation

Related results

Claimed proof

See also

References