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.

> Continue to Part 2

### Like this:

Like Loading...

*Related*

This entry was posted on June 30, 2007 at 11:49 am 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.

July 6, 2007 at 1:52 pm |

[…] my research, just because I think it’s cool), they’ve been running a rather interesting series of posts on forbidden minors and graph embeddings into surfaces. The forbidden minor […]

April 12, 2009 at 5:42 am |

[…] Graph Minor Theory, Part I « The Everything Seminar […]