**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.