Topological K_5's in Line Graphs

The line graph L(G) of a graph G has as its vertex set the edges of G, with two vertices adjacent if and only if the corresponding edges are adjacent. A topological K_5 is a subdivision of the complete graph on 5 vertices.

The line graph of any non-planar graph of minimum degree at least 3 contain a topological K_5.

Of course, if G contains a vertex of degree 5, then its line graph contains a K_5 subgraph. It is not hard to show that the line graph of any graph of minimum degree at least 3 and with a vertex of degree 4 contains a topological K_5. So it suffices to prove the above conjecture for cubic graphs. Similarly, using an argument involving small edge-cuts, it suffices to prove the conjecture for 3-connected cubic graphs. The assumption of nonplanarity is necessary, since the line graph of any cubic planar graph is also planar.

A natural approach would be to use the fact that every cubic non-planar graph contains a topological K_{3,3}. Indeed, the line graph of K_{3,3} is C_3 x C_3 which does contain a topological K_5. However, subdividing G can change whether or not its line graph has a topological K_5, so this approach might not be fruitful. For example, let G' be the graph formed from a cubic graph G by subdividing every edge. Then G' is of maximum degree 3, and so it does not contain a topological K_5.

The conjecture is known to be true for cubic graphs G contains a K_{3,3} with a spanning tree  with no degree 2 vertices.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA (with thanks to ?)

Send comments to

November 2003