Graph Minor Theory, Part 2

by Jim Belk

Recall that a graph is planar if it can be drawn on the plane without edge crossings. In the last post, I mentioned Kuratowski’s characterization of planar graphs:

Kuratowski’s Theorem. A graph is planar if and only if it has neither $K_5$ nor $K_{3,3}$ as a minor:

Kuratowski’s K_5 and K_3,3

(Here $K_5$ refers to the complete graph on 5 vertices, and $K_{3,3}$ is the complete bipartite graph on two sets of three vertices.)

I don’t know a really elegant proof of this theorem, but I do have some sense of why these two graphs are the right forbidden minors.

$K_{3,3}$ and the Jordan Curve Theorem

The basic topological property of the plane is the Jordan Curve Theorem — any closed loop separates the plane into two components. This has some interesting consequences for graph drawing.

A Copy of K4

The above graph consists of a single loop with two red edges attached. If we wish to avoid crossings, the red edges must be drawn on opposite sides of the loop. By the Jordan Curve Theorem, it follows that the red edges are in different components of the complement of the loop. In particular, the blue edge in the following graph always crosses the loop:

A Copy of K{3,3}

This graph is exactly $K_{3,3}$ . As you can see, the statement “ $K_{3,3}$ is not planar” is a graph-theoretic version of the Jordan Curve Theorem.

The Möbius Strip

One surface for which the Jordan Curve Theorem fails is the Möbius strip. This is the surface obtained by gluing joining two ends of a rectangle with a half-twist:

Möbius Strip

If you cut the Möbius Strip along its center loop, you get a single twisted cylinder:

Cutting a Möbius Strip

(There is a nice video of this on YouTube.) In particular, cutting the Möbius strip along the center loop doesn’t seperate it into two components. This makes it possible to embed $K_{3,3}$ in the Möbius strip without crossings:

K{3,3} on the Möbius Strip

What About $K_5$ ?

If $K_{3,3}$ represents the Jordan Curve Theorem, what is the role of the other forbidden minor, $K_5$ ?

It turns out that $K_5$ is somewhat less interesting than $K_{3,3}$ . To understand why, let us examine the proof that $K_5$ isn’t planar.

Theorem. $K_5$ is not planar.
Proof: This is a proof by contradiction. Suppose that you could draw $K_5$ on the plane without crossings, and consider a neighborhood of one of the vertices:

Vertex Neighborhood

We don’t know much about how the graph is drawn, but we do know that there are four edges coming out of this vertex. Consider what happens if we “split” the vertex in two:

Vertex Splitting

This result is new graph drawn on the plane, with one more vertex and one more edge than $K_5$ . This new graph is isomorphic to the middle graph shown below:

Proof that K5 is not planar

The contradiciton is that the new graph contains a copy of $K_{3,3}$ . Since $K_{3,3}$ can’t be drawn without crossings, neither can the splitting, and so neither can $K_5$ . $\,\,\,\,\square$

As you can see, $K_5$ is essentially just a tagalong to $K_{3,3}$ . Its failure to be planar doesn’t really convey any new topology.

Before ending this post, I should mention that $K_5$ can be drawn on the Möbius strip fairly easily. (Try this for yourself.) This leaves us with an important question: is there any graph that can’t be drawn on a Möbius strip?

> Continue to Part 3

About these ads

This entry was posted on July 1, 2007 at 11:54 pm and is filed under Basic Grad Student, Jim, Undergraduate. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Graph Minor Theory, Part 2”

ComplexZeta Says:
July 6, 2007 at 3:31 pm | Reply
A Möbius strip satisfies the six-color theorem (reference: Mathworld), so $K_7$ cannot be drawn on a Möbius strip.
Jim Belk Says:
July 6, 2007 at 6:35 pm | Reply
That is true, $K_7$ cannot be drawn on a Möbius strip, and neither can any other graph with chromatic number 7.

I haven’t talked about graph coloring in any of my posts, but it is known that every surface possesses a “color theorem” analogous to the four color theorem for the plane. For example, graphs on the Möbius strip require up to 6 colors, and graphs on the torus require up to 7 colors. (Click here for the general formula.) This provides a large class of graphs that cannot be drawn on any given surface.
Graph Minor Theory « Abner’s Postgraduate Days Says:
April 12, 2009 at 5:42 am | Reply
[...] Graph Minor Theory, Part II « The Everything Seminar [...]
El problema de las tres casas y los tres suministros y la banda de Möbius - Gaussianos Says:
January 29, 2013 at 10:15 am | Reply
[...] Graph Minor Theory, Part 2 en The Everything Seminar. [...]

The Everything Seminar