Graphs with a K_5 Subdivision



Kuratowski's Theorem says that a graph is planar if and only if it does not contain a subdivision of K_5 or of K_{3,3}. In a sense, the K_5 subdivision is not needed: every 3-connected graph is planar if and only if it does not contain a K_{3,3} subdivision. The following two conjectures aim to show that in a sense the K_{3,3} minor is not needed. The first is due to Carsten Thomassen, the second to Paul Seymour (private communication).

Conjecture [T1]: Let G be a 4-connected graph with n vertices and at least 3n-6 edges. Then G is planar if and only if it contains no subdivision of K_5.

Conjecture: A 5-connected graph is planar if and only if it does not contain a subdivision of K_5.

We note that K_{4,4} is 4-connected and non-planar, but does not contain a subdivision of K_5.

Both of these conjectures imply the following conjecture of Dirac.

Conjecture [D]: Any graph with n vertices and at least 3n-5 edges contains a subdivision of K_5.

Thomassen [T2] showed that any graph with n > 4 vertices and at least 4n-10 edges contains a subdivision of K_5. More strongly, Conjecture D was solved in its entirity by Mader [M].

References:

[D] G.A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69-80.

[M] W. Mader, 3n-5 edges do force a subdivision of K_5, Combinatorica 18 (1998), no. 4, 569--595.

[T1] C. Thomasssen, Kuratowski's theorem, J. Graph Theory 5 (1981) 225-241.

[T2] C. Thomassen, Some homeomorphism properties of graphs, Math. Nachr. 64 (1974) 119-133.


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05405 USA

Send comments to dan.archdeacon@uvm.edu

November, 1998. Updated May, 2005.