4
$\begingroup$

A graph is outerplanar if it is planar and can be embedded in the plane so that all vertices are in the boundary of the outer face.

The analogue of Kuratowski's theorem for outerplanar graphs is that a graph is outerplanar if and only if it has no $K_4$ or $K_{2,3}$ minors. The usual way to show that a graph is not planar is via Euler's formula. I am wondering if there is a clean way to show that $K_4$ and $K_{2,3}$ are not outerplanar.

2 Answers 2

9

Evidently so. Take one of your graphs. Place another point outside the graph and connected by new edges to each existing vertex. From $K_4$ you get a planar embedding of $K_5,$ so that is a contradiction. Do the same trick with $K_{2,3},$ this time connect the new vertex to just the three appropriate vertices to get a planar $K_{3,3},$ another contradiction.

http://en.wikipedia.org/wiki/Outerplanar_graph

  • 0
    Thanks, this is exactly what I was looking for.2011-10-19
1

See Problem 3 of http://austinmohr.com/Work_files/mohr%20hw3.pdf.