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:

Graph Minor

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:

Forbidden Minors for Trees

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:

Kuratowski’s K_5 and K_3,3

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

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: