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 and 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 is any surface, the graph property “can be drawn on 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 and , 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 is really just a tagalong to .

**Trivalent Graphs**

It seems to me that the primary problem with 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 and be trivalent graphs. Then is a minor of if and only if is a topological subgraph of .

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 has a finite list of “forbidden trivalent minors”, such that a trivalent graph has if and only if it has no element of 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:

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 is any graph obtained from by a sequence of elementary splittings. Here is the key fact:

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

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 be a graph, and let be a trivalent graph. Then is a minor of if and only if some maximal splitting of is a topological subgraph of .

In part 2, we saw that any elementary splitting of contains a copy of . This gives us the following:

**Trivalent Kuratowiski’s Theorem.** A trivalent graph is planar if and only if it doesn’t contain 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:

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.

July 5, 2007 at 5:16 pm |

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.

July 6, 2007 at 12:21 pm |

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 .

August 15, 2007 at 8:24 pm |

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.

August 24, 2007 at 9:03 pm |

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.

April 12, 2009 at 5:42 am |

[...] Graph Minor Theory, Part III « The Everything Seminar [...]