Five spokes squeezed into K5

Two graphs that will not lie flat ends with Kuratowski’s theorem: a graph can be drawn in the plane without crossings exactly when it contains no subdivision of $K_5$ or $K_{3,3}$ — no copy of either, with its edges allowed to be stretched into paths.

There is a second way for one graph to hide inside another, and it gives a second theorem with the same two graphs in it. Instead of stretching edges, squeeze connected clumps of points down to single points. A graph obtained that way, perhaps after deleting some points and edges, is a minor. Klaus Wagner proved in 1937 that a graph is planar exactly when it has neither $K_5$ nor $K_{3,3}$ as a minor.

The two theorems look like restatements of each other, and they are not. There is a graph that has $K_5$ as a minor and has no subdivision of $K_5$ anywhere in it, and it is the most famous small graph there is.

A graph ruled off the plane by its shortest cycle #

The Petersen graph has ten points and fifteen edges: an outer five-cycle, an inner five-pointed star, and five spokes joining them.

The counting argument that disposes of $K_5$ does not dispose of it directly. A flat drawing of a connected graph with $V$ points has at most $3V - 6$ edges, because each face is bounded by at least three edges and each edge borders two faces. For ten points that ceiling is twenty-four, and fifteen is well inside it.

But the Petersen graph has no triangles and no four-cycles. Its shortest cycle has five edges, so in any flat drawing each face would need at least five. Running the same count with five in place of three,

$$2E \ge 5F, \qquad V - E + F = 2 \quad\Longrightarrow\quad E \le \tfrac{5}{3}(V - 2) = 13\tfrac13,$$

and fifteen edges is too many. The graph is not planar, and a longer shortest cycle is what proves it. The general form of the ceiling is $E \le \frac{g}{g-2}(V - 2)$ for a planar graph whose shortest cycle has $g$ edges, and the familiar $3V - 6$ is the case $g = 3$.

The same formula with $g = 4$ is the bound that rules out $K_{3,3}$ in the first of these essays: no triangles, so $E \le 2(V - 2) = 8$, against nine edges. The Petersen graph is the next case in a sequence. It is the smallest graph in which every point has three neighbours and the shortest cycle has five edges — the $(3,5)$-cage — and it exceeds its girth bound by one and two-thirds edges, where $K_5$ and $K_{3,3}$ each exceed theirs by exactly one. Each of the three is ruled out by counting faces, with a different number of edges per face. What the counting cannot do is say which forbidden graph is inside, and on the Petersen graph that question has two different answers.

That settles planarity without naming an obstruction, which leaves the question of which one it contains. Kuratowski’s theorem says there must be a subdivision of $K_5$ or of $K_{3,3}$ in it. It cannot be $K_5$. A subdivision of $K_5$ needs five branch points with four paths leaving each, and every point of the Petersen graph has exactly three neighbours. So it has to be $K_{3,3}$ — and the graph also contains $K_5$ in the other sense.

Five spokes, and all ten joins #

Take the five spokes as clumps: each outer point together with the inner point it is joined to.

The count is quick. Two pairs whose outer points are neighbours on the cycle are joined by a cycle edge; there are five such. Two pairs whose outer points are two apart have inner points that are neighbours on the star; there are five of those too. Five pairs of clumps have exactly ten pairs between them, and every one is joined.

So $K_5$ is a minor of the Petersen graph and not a subdivision of any part of it. The difference is where degree goes. A subdivision preserves the degree of its branch points: a point of $K_5$ with four edges must be a point with four paths leaving it. A contraction adds degrees up. Each clump here has two points of degree three, one edge used inside the clump, and four edges leaving it, one to each other clump — degree four assembled out of two threes.

The copy of K3,3 that must be there #

Kuratowski’s theorem promises a subdivision of $K_{3,3}$ in the Petersen graph, and a search over six branch points and nine connecting paths finds one.

The search tries branch points of degree at least three — here every point qualifies — and routes the nine required paths one after another through points not yet used, backing up when a path cannot be completed. Each path found is checked to run along edges of the graph, and no interior point may appear on two paths or be a branch point. With ten points there are few enough choices that the search is complete: it finds this subdivision, and run for $K_5$, it stops immediately at the degree condition.

So both theorems are satisfied by the Petersen graph, through different graphs. Wagner’s sees a $K_5$ minor, and also a $K_{3,3}$ minor, since every subdivision is a minor. Kuratowski’s sees only the $K_{3,3}$. A theorem forbidding two subdivisions and a theorem forbidding two minors can agree on which graphs are planar only if a squeezed $K_5$ always leaves a stretched copy of something behind.

A point split in two #

The mechanism is visible on the smallest example. Take $K_5$ and replace one of its points by two points joined by an edge, sharing the old point’s four neighbours two and two.

The two halves of the split point go on opposite sides, each accompanied by the two old neighbours that belong to the other half. Then every cross pair is joined: each half to the other half and to its own two old neighbours, and each old neighbour to its own half and to the two old neighbours of the other half, which $K_5$ joined already. The six points and nine edges that result are exactly $K_{3,3}$, with no stretching needed; the two edges left over join old neighbours that ended up on the same side.

That is the whole of the argument that the two theorems agree, run on one point. Suppose a graph has $K_5$ as a minor. Each of the five clumps is connected, so it contains a tree reaching the four edges that leave towards the other clumps. Either that tree has a single point from which four separate paths reach the four edges — and then the clump behaves like a point of degree four, and if all five clumps do, the graph contains a subdivision of $K_5$ — or the tree’s paths to the four exits split two and two along a path inside the clump, exactly as the split point does, and then the edges around that clump contain a subdivision of $K_{3,3}$.

For $K_{3,3}$ there is nothing to prove: its points have degree three, a clump reaching three exits always has a point where the three routes separate, and a $K_{3,3}$ minor is always a $K_{3,3}$ subdivision.

Eight graphs searched both ways #

The two notions can be compared on small graphs by searching for every obstruction in every sense.

The minor search enumerates every connected set of points — at most a thousand for ten points — and builds families of five, or of six split three and three, that are disjoint and joined wherever the target graph has an edge. The subdivision search is the path-routing search above. Both return a witness when they succeed, and the witness is checked independently of the search that found it.

Three patterns are in the table, and each is a theorem in miniature. Every subdivision is also a minor: contract each path to a single edge. The $K_{3,3}$ columns agree row by row, for the degree-three reason. Having some obstruction is the same in both senses: a row has a yes somewhere in its minor columns exactly when it has one in its subdivision columns. The cube and the octahedron, both skeletons of solids and so drawable flat, have no yes anywhere. $K_6$ has everything.

The one extra graph Wagner needed #

Wagner’s 1937 paper went further than planarity, and the extra step explains why minors became the preferred language.

Which graphs have no $K_5$ minor? Planar graphs, certainly, and not only them: the Wagner graph has none and is not planar. Wagner showed that these two sources are all there is. Every graph with no $K_5$ minor can be assembled from planar graphs and copies of the Wagner graph by gluing along a point, an edge or a triangle, and deleting some of the glued edges afterwards.

That structure theorem is the reason the result mattered to him. It shows — six years before Hugo Hadwiger turned the observation into a conjecture — that the four-colour problem is a statement about $K_5$ minors: every graph with no $K_5$ minor can be coloured with four colours if and only if every planar map can. The gluing respects colourings — a triangle along which two pieces are glued can be matched up in both — and the Wagner graph is easily four-coloured, so everything reduces to the planar pieces. A question about maps became a question about which graphs contain which clumps. The planar pieces still need the full four-colour theorem; five colours come cheaply from Kempe’s chain argument, and the step from five to four is the one that took a computer.

The deeper reason to prefer minors came later, and it is where the two languages part for good. A family of graphs closed under taking minors is described by the minors it forbids, and Neil Robertson and Paul Seymour proved, in twenty papers ending in 2004, that the forbidden list is always finite. Graphs that embed on the projective plane — the disc sewn to a Möbius band — have 35 forbidden minors and 103 forbidden subdivisions. For the torus — a sphere with one handle, where seven regions can all touch — more than seventeen thousand forbidden minors are known and the complete list is not.

Why a finite list is a theorem and not a habit #

A finite list of forbidden minors is a statement with algorithmic content, and the content is stranger than it looks.

For planarity the list is two graphs long, and planarity can in any case be tested directly — John Hopcroft and Robert Tarjan found a linear-time test in 1974, and later linear-time tests return either a flat drawing or a Kuratowski subgraph as a certificate a reader can check. Robertson and Seymour showed more generally that for any fixed graph $H$, whether $H$ is a minor of a given graph can be decided in time polynomial in the graph’s size. Combined with the finite list, that means every minor-closed family has a polynomial-time membership test — for the torus, for any surface, for graphs that can be drawn in space with no two cycles linked.

The catch is that the proof of finiteness does not produce the list. It shows that an infinite sequence of graphs, none a minor of a later one, cannot exist, by an argument in the tradition of Kruskal’s theorem on trees; it does not say how long the list is or how to find it. So for the torus a polynomial-time test is known to exist, and nobody can write it down, because nobody has the complete list of obstructions it would check.

The logical strength involved is also unusual. Harvey Friedman, Robertson and Seymour showed in 1987 that Kruskal’s theorem cannot be proved in predicative systems of analysis, and that the graph minor theorem cannot be proved even in the stronger, impredicative system called $\Pi^1_1$-comprehension — the same territory an ordinal as a growth rate maps for Kruskal’s theorem, where the functions that measure these sequences grow past every tower. A statement about which finite graphs contain which smaller ones sits beyond the reach of ordinary induction, and the two forbidden graphs of planarity are its first and gentlest instance.

What a search on ten points cannot see #

Exhaustive at these sizes is exhaustive at these sizes. Every row of the table is complete for its graph and says nothing about an eleventh point. The theorem that minors and subdivisions agree on planarity is the argument about clumps and exits, and the search confirms the argument’s conclusion on eight cases without checking its steps.

A found subdivision is one of many. The figures draw the first $K_{3,3}$ the search reaches. The Petersen graph has a great many, related by its symmetries — which carry any path of three edges, taken in either direction, to any other — and a figure of one says nothing about how they are arranged.

Contraction is not drawn as a motion. The spokes figure puts the graph and its minor side by side, with colours standing in for the clumps. What a contraction does to a drawing — pulls two points together and merges their edges, possibly creating parallel edges that are then discarded — is not shown, and neither is the fact that contraction never destroys a flat drawing, which is why planar graphs are closed under minors in the first place.

The eight graphs were chosen, not sampled. They are the two obstructions, the smallest graphs on which the two notions part, one graph with everything, two planar skeletons and Wagner’s exceptional piece. A table of random graphs would say something about how often minors and subdivisions disagree, which is a different question — for large random graphs almost every graph has both obstructions in both senses, and the disagreement is a phenomenon of sparse graphs with low degree, where a subdivision has too few points of degree four to work with.

And the Petersen graph’s other famous properties are invisible here. It has no three-colouring of its edges although it is cubic and has no bridge, which makes it the smallest counterexample in the theory of matchings and edge-colourings. None of that is about planarity, and none of it appears in a search for obstructions.

Still open: Hadwiger’s conjecture beyond six #

Hadwiger’s conjecture is the general form of the $K_5$ case. Every graph with no $K_t$ minor can be coloured with $t - 1$ colours.

For $t$ up to 4 it is elementary. For $t = 5$ it is equivalent to the four-colour theorem, by Wagner’s gluing argument, and so it is true by a computer-assisted proof. For $t = 6$, Robertson, Seymour and Robin Thomas proved in 1993 that it again reduces to the four-colour theorem, by showing that a minimal counterexample would be a planar graph with one extra point attached to everything. From $t = 7$ on it is open.

The known bounds are far from $t - 1$. It has been known since the 1980s that graphs without a $K_t$ minor can be coloured with a number of colours growing like $t\sqrt{\log t}$, and a series of results since 2019 has brought that down to $t \log \log t$ times a constant. The conjecture asks for $t - 1$, and no argument is known that achieves any linear bound. It is widely regarded as one of the deepest open problems in graph theory, and the step it is stuck on is precisely the one Wagner’s structure theorem took for $t = 5$: describing what a graph without a $K_t$ minor looks like well enough to colour it.

An obstruction measured by what can be merged #

The habit worth keeping is to ask which kind of containment an obstruction theorem uses, because the choice decides what the theorem can grow into.

Subdivisions are the natural first choice. They preserve the picture: a stretched $K_5$ inside a drawing is visibly a $K_5$ with bent edges, and a crossing that $K_5$ forces is a crossing the larger drawing inherits. Kuratowski’s proof is geometric in exactly that way.

Minors lose the picture and keep something better. A minor can be created by degrees adding up across a clump, so it sees obstructions a subdivision misses, as the Petersen graph shows. And because contracting and deleting commute and compose, minor-closed families have the finite forbidden lists that make a theory. The two notions happen to agree for the plane. For every other surface, and for colouring, only one of them organises the answers.