Before starting this post, I have to warn you that it will be getting somewhat technical. I should also say that I’m not an expert in this area. I learned much of what I’m talking about by reading Graphs on Surfaces by Bojan Mohar and Carsten Thomassen.
Last time I promised that I would try to explain the six forbidden trivalent minors for the projective plane. To start, let me present some new drawings of these minors:
These are the same six graphs (drawn in the same order) as in the previous post, and the colors are designed only to highlight the structure. The drawings above are “maximally symmetric”, in the sense that you should be able to see the entire symmetry group of the graph. For example, the fifth graph consists of a 9-gon with three tripods attached, and you can see that any rotations or reflection of the 9-gon is possible by permuting the three tripods.
The Role of
The key to understanding embeddings of trivalent graphs in the projective plane is to understand the role of . First observe the following:
Theorem. Any trivalent graph that cannot be embedded in the projective plane contains a copy of .
Proof: Observe that any planar graph embeds on the projective plane as well. Therefore, any trivalent graph that does not embed on the projective plane is not planar, and therefore contains . (This was the trivalent Kuratowski theorem from part 3.)
In particular, each of the six forbidden minors drawn above contains in several different ways. Indeed, the first of the forbidden minors is just a disjoint union of two copies of :
The fact that this graph is forbidden is roughly equivalent to the following theorem:
Embedding Theorem. Any embedding of in the projective plane separates it into four discs. Indeed, there is only one embedding of in the projective plane up to homeomorphism:
(In the picture above, the four discs are the central hexagon, together with three squares that each cross the boundary circle.)
This theorem represents a fundamental topological property of the projective plane, a sort of analogue of the Jordan curve theorem. I’m not going to give a proof, but you ought to be able to prove it yourself if you play with it for a few minutes.
Understanding the Forbidden Minors
Let’s try to get a sense of why the other five minors are forbidden. We’ll start with the first one, which has several different copies of sitting inside of it:
We have highlighted one copy of in red, with the remaining three edges in blue. Watch what happens when we try to draw this graph on the projective plane:
By the embedding theorem, we have essentially no choice in how to draw the red edges. As you can see, there is no way to draw the blue edges that avoids crossing the red ones, and therefore this graph cannot be embedded in the projective plane.
A similar proof works for each of the forbidden minors. For example, here is a drawing of the third forbidden minor:
Again, the red edges form a copy of , with the complement in blue. The blue subgraph is attached at four places to a single red edge, and the order of attachment makes it impossible to avoid crossings:
Here are some drawings of the final three forbidden minors:
Again, these were obtained by first finding a copy of inside of the minor, and then attaching the edges of the complement to a drawing of in the projective plane. In each case, the way in which the blue edges are attached to the red ones forces them to cross.
There is a slight problem with the reasoning we have been using. As I have stated, there is only one embedding of in the projective plane “up to homeomorphism”. To be precise:
Embedding Theorem (Precise). Given any two embeddings , there exist homeomorphisms and such that .
The important thing is that a graph automorphism may be required for this equivalence. In particular, a labelled copy of has six different embeddings, corresponding to six different automorphisms of :
This is important, because these six embeddings give six different possible ways of attaching the extra edges. For example, here was the drawing presented for the last forbidden minor:
Clearly the blue edges must cross in this embedding of , but to show that this graph can’t be drawn on the projective plane we must consider each of the six embeddings. This turns out not to be a problem: the blue tripod must lie in the central hexagon to avoid crossings, and then the picture is exactly as shown.
Incidentally, the reason that there are six different embeddings is that there are precisely six hexagons in the graph .
So far, we have shown that the six minors presented at the beginning of this post are in fact forbidden. What we have not shown is that these graphs suffice, i.e. that any trivalent graph that doesn’t embed in the projective plane contains one of these six.
The problem is, I don’t really understand why this is true. It is proven rigorously in this paper, but the details seem complicated, and I am left without a deep understanding. In addition to the obvious reasons, I have an ulterior motive for wanting to understand this subject better:
Open Problem. Find the forbidden trivalent minors for the torus.
Ideally, a good understanding of the six trivalent forbidden minors for the projective plane would shed some light on those for the torus. There is good reason to think that the two cases are similar:
Embedding Theorem. Any embedding of on the torus separates the surface into three discs.
While I’m on the subject of open problems, I should mention a conjecture related to what we’ve been talking about:
Negami’s Conjecture. A graph embeds on the projective plane if and only if some finite cover of the graph embeds on sphere.
Note that embedding on the sphere is the same as embedding on the plane, so the conjecture is that a graph is projective if and only if some finite cover is planar. It’s not hard to see that “having a finite planar cover” is minor-closed, so it suffices to check that none of the forbidden minors for the projective plane has one. This has been proven for all but one of the minors (see these papers):
Theorem (Mohar and Hlineny). Negami’s conjecture holds if and only if has no finite planar cover.
is a (non-trivalent) forbidden minor for the projective plane. Note that is the 1-skeleton of the octahedron, so is the 1-skeleton of the cone of the octahedron.
As far as I know, no one has tried to prove Negami’s conjecture for trivalent graphs. Of the six forbidden trivalent minors, I think that the fourth is the only one that has as a minor. Therefore:
Observation. Negami’s conjecture holds for trivalent graphs if and only if the following graph has no finite planar cover: