Variations on Graph Minor

Introduction

Reinhard Diestel, in his well known text, says of the principal theorem in relatively recent work by Neil Robertson and Paul Seymour that it is "one which dwarfs any other result in graph theory and may doubtless be counted among the deepest theorems that mathematics has to offer." I'll try to give here a very rough idea of what this is all about.

A topological puzzle

Sometime while I was in high school someone showed me the following geometrical puzzle. You were given the location of three refineries and three oil wells in an empty desert, and the puzzle required you to lay out pipeline routes from each refinery to each well, with the highly restrictive condition that the pipelines couldn't cross.

Thus the obvious solution of laying out the pipelines on the direct routes wasn't allowed, since it involved lots of pipeline crossings.

By pure coincidence, I was at this time reading the book What is Mathematics by Richard Courant and Herbert Robbins, and I was extremely excited to realize that there were a number of things that the book discussed that were relevant to the puzzle. The first was that this was a topological problem, which meant that the exact position of the refineries and wells didn't make any difference. You could imagine the desert as being, in the term used by Courant and Robbins, a rubber sheet which you could deform to your heart's content. Now if you start out working on the puzzle in a careful manner, you wonder quite soon what kind of choices you have in connecting just two refineries and two wells. A first attempt might look like this:

but then by topological deformation you can make it into this:

There is a second possibility for the first picture, with the loop going around the other way, but this also leads to the same diagram. In other words, any layout of pipes

must be topologically a circle. Solving the puzzle therefore means placing well #3 and refinery #3 and various pipelines relative to this layout. Let C be the closed curve these pipes trace. It is a simple curve in that it does not cross itself.

To the amazement and even disbelief of my high school friends, solving the puzzle turns out to be impossible. The idea that impossibility could be proved was to them rather hard to swallow. Whereas I myself was not all that surprised, since Courant and Robbins had a clear discussion of the famous Königsberg bridge puzzle, which is also impossible. Almost miraculously, Courant and Robbins also had a discussion of the general principle that lay behind the impossibility:

Jordan curve theorem. Any simple closed curve in the plane (such as C) divides the plane into two regions - inside and outside - and any path from a point in one region to a point in the other must cross C .

Thus, suppose the third well is located inside C. The exact location doesn't matter, topologically speaking.

And, again topologically, any layout of pipelines from the new well to the old refineries looks like this:

But now some experimentation will lead you to realize that no good placement of the third refinery is possible - any placement at all will find it separated from one of the wells by a closed curve traced out by pipelines already laid. The best we can do is reduce the number of intersections to one.

Plane graphs

An abstract graph is a set V together with a set E of pairs of distinct elements (u, v) in V. The elements of V are the vertices or nodes of the graph and those of E are its edges. In the previous section V is made up of the wells and refineries, and there are edges between each well and each refinery. This defines what is called the complete bi-partite graph K_3,3 since the vertices are of two types and there are edges from each of one type to each of the other. A graph is called planar if it can be drawn in the plane without its edges crossing, so the reasoning of the previous section amounts to a proof that:

Proposition. The graph K_3,3 is not planar.

Another important example of a graph is the complete graph K_n with n at least 3. It has N vertices and an edge between every two distinct vertices. Here, for example, are K₃, K₄, and K₅:

The graphs K₃ and K₄ are planar, but an argument similar to that in the previous section shows that:

Proposition. The graph K₅ is not planar.

If a graph is planar, then so is any graph contained in it. Thus a consequence of the two results above is that any graph that contains either a copy of K_3,3 or one of K₅ isn't planar. Around 1930, the Polish mathematician Kuratowski proved a remarkable converse:

Theorem. Any graph that cannot be drawn in the plane contains a copy of K_3,3 or of K₅.

I haven't said exactly what I mean by 'contained in', and in fact there are several possible interpretations for which Kuratowski's Theorem remains valid. At the time Kuratowski wrote, neither topology nor graph theory had been quite so formalized as they have been since, and for him containment meant topological equivalence, i. e. an equivalence of the configuration of edges without requiring that nodes correspond. The more modern definition is in terms of subgraphs and graph subdivision. A subgraph of a graph is obtained from it by repeating these processes: (a) deleting an edge and (b) deleting an isolated vertex. A subdivision of a graph is obtained from it by repeatedly adding a node to the interior of an edge. If a graph G contains as a subgraph a subdivision of another graph H, then H is said to be a topological minor of G. For example, the Petersen graph

contains as topological minor the graph K_3,3, indicated by the picture

which exhibits in another form the graph

We then have the precise formulation:

Kuratowski's Theorem A graph is non-planar if and only if it contains either K_3,3 or K₅ as topological minor.

There is another formulation of more current interest. A graph minor (usually just minor for short) of a given graph is one obtained from a subgraph by repeating the process of contracting an edge and then eliminating duplicate edges and loops. Thus a graph is a minor of any of its subdivisions And the graph K₅ is a minor of the Petersen graph, obtained from it by contracting all radial edges. The 'new' formulation of Kuratwoski's theorem, first stated by Klaus Wagner in 1937, is that a graph is non-planar if and only if it has either K₅ or K_3,3 as a graph minor. This turns out to be the most fruitful version.

It is easy to verify that if the graph G has a planar embedding and has H as graph minor then H is also planar. Thus the family of planar graphs is graph-minor-closed. The results of Robertson and Seymour generalize Kuratowski's Theorem to the much larger and still fascinating class of graph-minor-closed families.

Wagner's conjecture

Suppose for the moment that C is any partially ordered set of objects satisfying the descending chain condition: Any strictly decreasing chain in C must be finite. A subset D of C is called closed if it satisfies this condition:

and open if it is the complement of a closed set. If E is an open set, let Min(E) be the subset of minimal elements in it. Because of the descending chain condition, any open set E can be characterized as the set of all b in C that are greater than or equal to some element of Min(D).

This is enjoyable to verify.

The set of all graphs is partially ordered by the graph minor relationship: H < G if H is a proper graph minor of G. This certainly satisfies the descending chain condition, since the size of a proper graph minor is smaller than that of the original. If F is a graph-minor closed family of graphs, the minimal graphs in its complement are called its excluded or forbidden minors. The main result of Robertson and Seymour has three versions:

• The set of forbidden minors of any infinite graph-minor-closed family of graphs is finite.
• In any infinite graph-minor-closed family of graphs there exist H and G with H < G.
• In any infinite graph-minor-closed family of graphs there exists a strictly increasing chain.

This was apparently conjectured by Klaus Wagner in the thirties, but not explicitly found in print until much later.

The proof is highly non-constructive, and requires the Axiom of Choice. Finding in any given example an explicit set of excluded minors is often a challenging problem with an interesting answer. Much energy has been spent on such problems with overall mixed success. Subsequent experience has made Kuratowski's theorem all the more remarkable.

Other surfaces

Kuratowski also observed that the graphs K_3,3 and K₅ are forbidden on the plane, they can be drawn on all other closed surfaces. The real projective plane can be realized as a disk with opposite points identified, and here is the corresponding embedding of K_3,3:

while the torus can be obtained from the square by identifying opposite sides, and here is the corresponding embedding of K₅:

In general, the family of graphs that can be embedded in a given closed surface such as the real projective plane or the torus is graph-minor-closed, and therefore by the theorem of Robertson and Seymour possesses a finite set of excluded minors. This set has been explicitly calculated for the real projective plane, but for no other surface. This is one of the interesting open questions in the subject, particularly as there do exist efficient algorithms that tell whether or not a given graph may be embedded in a given surface.

Many forbidden minors are known already for the torus, and the number is known to grow rapidly with the genus. The case of the projective plane exhibits one interesting feature - if one restricts consideration to topological minors then the excluded list has 103 minimal elements, whereas there are only 35 excluded graph minors. The much smaller size expected for excluded graph minors is one motivation for dealing with them.

References

• Dan Archdeacon, a web page on torus embeddings.

• Richard Courant and Herbert Robbins, What is Mathematics, Oxford University Press, 1941.

  A new edition, with revisions by Ian Stewart, was issued in 1996, but I haven't seen it. To tell the truth, I find it hard to imagine what improvements could have been made in this classic.

• Reinhard Diestel, Graph Theory, third edition, Springer-Verlag, 2005.

  This is also available at Diestel's web site as a .pdf file, but with printing disabled. The last chapter in the book is an admirable brief exposition of the work of Robertson and Seymour.

• Casimir Kuratowski, Sur le problème des courbes gauches en Topologie, Fundamenta Mathematica 16 (1930), 271-283.

  It is interesting to see how the basic notions of topology and graph theory have been fruitfully disentangled since this was written.

• László Lovasz, Graph minor theory, Bulletin of the American Mathematical Society, 43 (January 2006), 75-86 (available in .pdf format).

  This is a concise and admirable discussion. WEagner's conjecture si reminiscent of König's Lemma, which says that in any locally finite rooted tree there exists an infinite branch. This amounts to weak version of the axiom of Choice, so it should not be surprisng taht the proof of Wagner's conjecture involves the Axiom of Choice. One of the good features of Lovasz's article is that it gives some idea of the flavor of the result of Robertson & Seymour by explaining in some detail an earlier but related result of Kruskal about trees. The proof of this by Nash-Wilson, which Lovasz sketches, is short and shows as well why the Axiom of Choice is necessary. It also motivates the proof of the result of Robertson & Seymour.

• Bohan Mohar, Graph minors and graphs on surfaces, available at Citeseer. Among other good features, this lists all the Graph Minor series of Robertson & Seymour.

• Bohan Mohar, What is a graph minor, to appear in the Notices of the American Mathematical Society.

• Bohan Mohar and Carsten Thomassen, Graphs on surfaces, Johns Hopkins University Press, 2001.

  A thorough book with much related material of great interest, such as circle packings.

• Neil Robertson and Paul Seymour, Graph minors XIII. The disjoint paths problem, Journal of Combinatorial Theory 63 (1995), 65-110.

  This is one of a series of papers, all but one in the same journal, starting with Graph Minors I. Excluding a forest in 1983 and ending with Graph minors XX. Wagner's conjecture in 2004.

• Robin Thomas, Planarity in linear time, at Thomas' home page.

  The ideal proof of Kuratowski's theorem explains an algorithm that either constructs a planar embedding of a given graph or exhibits either K_3,3 or K₅ as a graph minor. This short note, comes fairly close to doing this, although because it has no pictures its explanation is somewhat obscure.

• Klaus Wagner, , Deutsche Mathematik 2 (1937), 280-285.

  One of a several pioneering papers by Wagner from the late 1930's. It contains the original enunciation of Kuratowski's theorem in terms of graph minors, and is quite pleasant to read - with the interesting feature, unusual in mathematics at that time, that it is printed in Fraktur.

  This odd feature is significant. This journal is famous - even notorious - but for non-mathematical reasons. It was founded by Ludwig Bieberbach in the year 1936, in order to demonstrate what "pure" German mathematics could be, and I imagine such mathematics required a pure German font. The journal folded, during the war that followed shortly upon its foundation, after seven years. Many people have written about these troubled times and this troubled project. Relevant references can be found at the page on Bieberbach at the history web site of the University of St. Andrews.