Graph Minor Theory, Part 3

by Jim Belk

Okay, after two very expository posts I’m ready to get at something less elementary: forbidden minors for embeddings on surfaces. I’m going to need to assume some additional background, including the classification of closed surfaces:

Orientable: Sphere, Torus, 2-Holed Torus, etc.

Non-Orientable: Projective Plane, Klein Bottle, etc.

Topologists generally prefer to talk about embeddings of graphs in closed surfaces. For example, we draw graphs on the sphere instead of on the plane (a sphere is just a plane with an extra point an infinity), and we similarly prefer the projective plane to the Möbius strip.

Note: The projective plane is the surface you get by gluing together a Möbius strip and a disc along their boundaries. It can be represented as a single disc with opposite points on the boundary identified. For example, here are embeddings of $K_5$ and $K_6$ on the projective plane:

K5 and K6 on the Projective Plane

(The second is the projective version of the icosahedron.) Note that you can get the Möbius strip back from the projective plane by removing any disc.

Forbidden Minors for Surfaces

If $S$ is any surface, the graph property “can be drawn on $S$ without crossings” is minor closed. (Removing edges is easy, and you can contract edges on a surface by dragging the endpoints together.) For the sphere, the forbidden minors are $K_{3,3}$ and $K_5$ , which is essentially a statement of the Jordan curve theorem. What are the forbidden minors for the other closed surfaces?

The answer is annoyingly complicated. There are 35 different forbidden minors for the projective plane, and these have been computed explicitly. (See Mohar and Thomassen, pg. 198 for the complete list.) The torus seems to have hundreds of forbidden minors, and the complete list is not yet known. It is known that the number of forbidden minors grows exponentially with genus, so the forbidden minors for the Klein bottle and two-holed torus presumably number in thousands.

I have always found this situation extremely disappointing. As a topologist, I am interested about these questions primarily because I want some insight into the topology of these surfaces. What do the 35 forbidden minors for the projective plane say about the surface? Can we find any statements analogous to the Jordan Curve Theorem? Is there any conceptual way to understand these graphs?

I claim that there is. In particular, I’d like to argue that most of the 35 forbidden minors are “tagalongs” in the same way that $K_5$ is really just a tagalong to $K_{3,3}$ .

Trivalent Graphs

It seems to me that the primary problem with $K_5$ is that its vertices have degree four. From a topological point of view, a vertex of degree four represents a huge coincidence. For example, the 1-skeleton of the continental United States has only one vertex of degree four, and the 1-skeleton of the Earth partitioned into nations has none. In some sense any “naturally occurring” graph on a surface is trivalent, meaning that every vertex has degree three.

Trivalent graphs interact particularly nicely with minor theory. This is due to the following two theorems:

Theorem 1. Let $G$ and $H$ be trivalent graphs. Then $G$ is a minor of $H$ if and only if $G$ is a topological subgraph of $H$ .

Here a “topological subgraph” is a subgraph obtained by removing edges and then forgetting any vertices of degree two. (That is, you un-subdivide any subdivided edges.)

Theorem 2. The forbidden minor theorem holds for the class of trivalent graphs. That is, any minor-closed property $P$ has a finite list $\mathcal{F}$ of “forbidden trivalent minors”, such that a trivalent graph has $P$ if and only if it has no element of $\mathcal{F}$ as a topological subgraph.

Neither of these theorems is very hard to prove. Define an elementary splitting of a graph to be the reverse of an edge contraction:

Elementary Splitting

In the elementary splitting above, note that the eight edges incident on the original vertex were split into a group of five and a group of three. A different partition of these edges would give a different elementary splitting.

A splitting of a graph $G$ is any graph obtained from $G$ by a sequence of elementary splittings. Here is the key fact:

Key Fact. Let $G$ and $H$ be graphs. Then $G$ is a minor of $H$ if and only if some splitting of $G$ is a subgraph of $H$ .

This is a consequence of the fact that you can obtain a minor of a graph by first doing edge removals and then edge contractions.

Note that an elementary splitting has no effect on a trivalent graph (assuming you ignore the new vertex of degree two). Indeed, if you start with any graph and perform a sequence of elementary splittings, you will eventually arrive at a trivalent graph, which will be a maximal splitting of the original. The two theorems above can be proven fairly easily from the following lemma:

Lemma. Let $G$ be a graph, and let $H$ be a trivalent graph. Then $G$ is a minor of $H$ if and only if some maximal splitting of $G$ is a topological subgraph of $H$ .

In part 2, we saw that any elementary splitting of $K_5$ contains a copy of $K_{3,3}$ . This gives us the following:

Trivalent Kuratowiski’s Theorem. A trivalent graph is planar if and only if it doesn’t contain $K_{3,3}$ as a topological subgraph.

As you can see, restricting to trivalent graphs simplifies the forbidden minors on the plane. It also works amazingly well for the projective plane:

Surprising Theorem. A trivalent graph embeds on the projective plane if and only if has none of the following as a topological subgraph:

Forbidden Trivalent Graphs for the Projective Plane

Thirty-five forbidden minors, but only six forbidden trivalent subgraphs! Maybe there is some hope of understanding embeddings of graphs on the projective plane. Next time we’ll explore the topological structure of these graphs, and figure out what these graphs have to say about the topology of the projective plane.

Note: In case you’re curious, I found these six graphs by searching through Dan Archdeacon‘s Thesis (the PDF is online), which has the complete list of 103 forbidden subgraphs for the projective plane. Since any subgraph of a trivalent graph is trivalent, the forbidden trivalent minors are precisely the six trivalent graphs from this list.

> Continue to Part 4

About these ads

This entry was posted on July 4, 2007 at 4:09 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.

5 Responses to “Graph Minor Theory, Part 3”

Greg Muller Says:
July 5, 2007 at 5:16 pm | Reply
Is there any reason you wrote the last two forbidden minors of the projective plane differently than when we were working on it? Its an interesting way of drawing them.
Jim Belk Says:
July 6, 2007 at 12:21 pm | Reply
Not in particular — they were just easier to draw that way. Looking at them now, I suppose the rectangle form makes it more obvious that they contain several different copies of $K_{3,3}$ .
luke Says:
August 15, 2007 at 8:24 pm | Reply
I must say I do like the attempt to understand the surfaces better by thinking of trivalent, ie cubic, graphs. However, I thought I would note that there is no easy translation between a list such as Archdeacon’s and the list of cubic graphs. If anything that is an amazing coincidence, because it’s not true that a subgraph of a trivalent graph is trivalent.
Jim Belk Says:
August 24, 2007 at 9:03 pm | Reply
I should explain that point better — the statement “every subgraph of a trivalent graph is trivalent” was a bit imprecise.

I’m a topologist, so when I say “graph” I usually mean “topological graph” (i.e. a topological space homeomorphic to a 1-complex) as opposed to “combinatorial graph”, which is a slightly different concept. For example, from the topological point of view there’s no such thing as a bivalent vertex, since there’s no way to distinguish such vertices from the interior points of edges.

When talking about embedding in surfaces, it also makes sense to rule out univalent vertices, since an edge that ends in a univalent vertex can be removed without affecting embeddings of a graph. From the topologist’s point of view, the minimum reasonable degree for a vertex is three, and the statement “every subgraph of a trivalent graph is trivalent” is trivially true.

Minor theory works from both points of view. In particular, call a combinatorial graph “topological” if every vertex has degree at least three. Then every graph has a unique maximal topological minor (obtained by repeatedly contracting edges that possess univalent or bivalent endpoints). The topological graphs form a nice sublattice of the lattice of graphs, and the forbidden minor theorem holds as long as you are considering minor-closed properties that depend only on topology.

Incidentally, Archdeacon’s thesis has roughly the same conception of graphs that I do. His “forbidden subgraphs” are actually “forbidden topological subgraphs”, with bivalent vertices not allowed. (If you required subgraphs to be combinatorial and allowed bivalent vertices, the list of forbidden subgraphs would be infinite, since any subdivision of a graph on the list would have to be on the list.) Indeed, none of his 103 graphs has any bivalent or univalent vertices, which makes my reasoning valid.
Graph Minor Theory « Abner’s Postgraduate Days Says:
April 12, 2009 at 5:42 am | Reply
[...] Graph Minor Theory, Part III « The Everything Seminar [...]

The Everything Seminar