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