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

**
Conjecture:** T

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

Send comments to *dan.archdeacon@uvm.edu*

November 2003