One of my favorite theorems in mathematics is the Forbidden Minor Theorem from graph theory. For me, a graph is a 1-complex (i.e. an object made of vertices and edges, with loops and multiple edges allowed). A minor of a graph is anything you get by removing and/or contracting edges:
In the above example, we obtain a minor of the graph on the left by removing one edge and then contracting another. The resulting minor is a sort of squished subgraph of the original.
A property of graphs is minor closed if, whenever a graph has property , every minor must also have property . For example, the following properties are minor closed:
- Property : the graph is a tree (or disjoint union of trees)
- Property : the graph is planar (i.e. can be drawn on the plane without edge crossings)
Note that any graph without property must contain a cycle, and therefore has the loop as a minor:
Indeed, property (being a tree) is equivalent to not having the loop as a minor. There is a similar statement for property :
Kuratowski’s Theorem. A graph is planar if it only if it has neither of the following as a minor:
In each case, the disallowed graphs are called forbidden minors. The forbidden minor for property is the loop, and the forbidden minors for property are and . We are now ready to state the forbidden minor theorem:
Forbidden Minor Theorem (Robertson and Seymour). Any minor-closed property has a finite list of forbidden minors. That is, for any minor-closed property , there exist finitely many graphs , such that a graph has property if and only if it doesn’t have any of as a minor.
The proof of this theorem is spread out over twenty papers of Robertson and Seymour, published over a period of twenty years (1983-2004). It is at once simple and mysterious: Why should there only be finitely many forbidden minors? What are the forbidden minors for <insert your favorite here>? What property do you get if you forbid <insert your favorite list of graphs here>? I don’t feel like the answers to any of these questions are particularly well-understood (except perhaps by Robertson and Seymour). They’re certainly not well-understood by me.
Next time I’ll talk about my favorite minor-closed property: whether a graph can be drawn without crossings on a Möbius strip.