Ce billet est la traduction d’un billet écrit initialement en français : TPA – Planarité, mineurs et donuts.

Let’s have a little bit of graph theory today – I want to present (without a proof) a fun result about graph planarity. Which means – first, let’s define a few things and draw a few pictures.

A graph is a set of vertices (“points”) connected by edges. To describe a graph, I can say “the set of vertices is labeled 1, 2, 3, 4 and 5, and I have edges between edges 1 and 2, 2 and 3, 3 and 4, 4 and 1, 1 and 3, 2 and 4, 1 and 5, and 4 and 5”. I can also draw it on a sheet of paper, and I can draw that statement in different ways: all the drawings here are drawings of the graph I just described.

In these three drawings, two of them are plane: the graph is drawn such that edges of the graph do not cross. The first drawing is not plane: the edges 1-3 and 2-4 are crossing. A graph that can be drawn in the plane (that is to say, on a flat piece of paper) such that no two edges cross is called a planar graph. The fact that we have an adjective for such a graph should tell you that there exists non-planar graphs: graphs that cannot be drawn in the plane without crossing two edges. Two typical (and useful) examples are the complete graph on 5 vertices (5 vertices, and all possible edges) – denoted , and the complete bipartite graph on 3×2 vertices (2 groups and of three vertices, and all possible edges between vertices of group and vertices of group ), denoted . Here are their “usual” drawings; as we saw in the previous figure, these drawings are not unique. But you can search for a long long time for a drawing where no two edges cross (and not find it).

And there is a theorem (Wagner, 1937) that says that if a graph is not planar, it’s because somewhere in its structure it contains something that looks like or . More precisely:

A finite graph is planar if and only if it does not have or latex as a minor.

Okay, I cheated a bit, because I haven’t defined minor yet. So let’s do that:

A minor of a graph is a graph that is obtained from by doing any number of the following operations: removing an edge; removing a vertex; contracting a vertex.

Removing an edge is easy: if two vertices are connected by an edge, we can decide that in fact they aren’t, and remove the edge. Removing a vertex is also easy: pick a vertex, remove it, and remove all the edges that are connected to it, because otherwise we don’t know where they’re going anyway. Contracting a vertex is a tiny bit more complicated: the idea is that we pick two vertices that are connected with an edge, and we “merge” them in a single vertex. The resulting vertex is connected to all the edges of the initial two vertices that were in the original graph. One can imagine “pinching” the two vertices that get closer and closer until BOOM they fuse together. For a small example, in which I contract the vertices connected by the red edge in a single vertex:

So what Wagner says is: “if I fiddle with a graph a bit and I manage to obtain or , then I cannot draw the graph without crossing edges. But if I cannot get or , then I can draw the graph without crossing.”

There’s a theorem that expands this idea of “forbidden minors”. It’s a theorem by Robertson and Seymour, and its proof spans over 20 papers, published from 1984 to 2003. The theorem is stated as follows:

Every family of graphs that is closed under minors can be defined by a finite set of forbidden minors.

Let’s explain. A family of graphs that is closed under minors is a set of graphs such that, if I take any graph in this family, and I take a minor of it (with the aforementioned definition), then the minor is also in that set of graphs. What Robertson and Seymour say is that, in such a family, there exists a finite set of forbidden minors: if a graph has a minor of that set, then that graph is not part of the family.

Wagner’s theorem is a restriction of Robertson-Seymour for planar graphs. Planar graphs are a family of graphs that is closed under minors: if I take a minor of a planar graph, I can still draw that minor without crossing any edge, so it is planar as well. And there is a finite set of forbidden minors, specifically or : if I find one of these minors in a graph, then the graph is not planar. Wagner, for the case of planar graphs, actually states the forbidden minors explicitly, which Robertson-Seymour does not.

And that’s the fun part: in general, we do not know the forbidden minors in question. We know they exist; we know there’s a finite number of them, but we do not know which they are. And, for a tiny example as a conclusion of this post: suppose now that I want to draw a graph not on a sheet of paper, but on a torus – or, if you want, on a donut.

The idea would be to draw vertices on a donut, and to connect them with edges, exactly as I do in the plane. If I do that, and I can draw the graph without crossing edges, the graph is not planar anymore, but toroidal (or donutoidal if you want). The family of toroidal graphs is closed for minors, so there exists a set of forbidden minors for this family. So far, 17523 have been found. It is yet unknown how many there are in total. Fun, isn’t it?

(And if you want to find them all, you may want to start by making donuts.)