## Graph Minor Theory, Part I

by

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 $P$ of graphs is minor closed if, whenever a graph has property $P$, every minor must also have property $P$. For example, the following properties are minor closed:

• Property $T$: the graph is a tree (or disjoint union of trees)
• Property $Pl$: the graph is planar (i.e. can be drawn on the plane without edge crossings)

Note that any graph without property $T$ must contain a cycle, and therefore has the loop as a minor: Indeed, property $T$ (being a tree) is equivalent to not having the loop as a minor. There is a similar statement for property $Pl$:

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 $T$ is the loop, and the forbidden minors for property $Pl$ are $K_5$ and $K_{3,3}$. 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 $P$, there exist finitely many graphs $F_1,\ldots,F_n$, such that a graph has property $P$ if and only if it doesn’t have any of $F_1,\ldots,F_n$ 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 $P$ 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

### 2 Responses to “Graph Minor Theory, Part I”

1. Secret Blogging Seminar The math blog revolution marches on… « Says:

[…] 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 […]

2. Graph Minor Theory « Abner’s Postgraduate Days Says:

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