Two trees, and every edge in exactly one of them

A cube has eight corners, twelve edges and six faces, and $8 - 12 + 6 = 2$. The first rung of this ladder gets that answer by squashing the solid flat and then dismantling it, one edge at a time, checking at each step that the alternating sum has not moved. It works, and it leaves a question standing: why two?

Here is an argument that answers it, and it removes nothing.

Twelve edges, split into seven and five. Seven is $8-1$ and five is $6-1$, which is $V-1$ and $F-1$, and the fact that they add to $E$ is the formula:

$$E = (V-1) + (F-1) \quad\Longleftrightarrow\quad V - E + F = 2.$$

The two goes in at the start rather than coming out at the end. It is two because a tree on $k$ nodes has $k-1$ edges, twice.

What a spanning tree is, and why it has $V-1$ edges #

A tree is a connected graph with no loops in it. The one fact needed here is that a tree on $k$ nodes has exactly $k-1$ edges, and the reason is a counting argument worth having: start with one node and no edges, and grow the tree by adding a node at a time, each attached by one new edge. Every node after the first costs exactly one edge, so $k$ nodes cost $k-1$ edges. No loop is ever created, because a new edge always goes to a node that was not there before.

A spanning tree of a graph is a tree inside it that reaches every vertex. Every connected graph has one — grow it greedily, refusing any edge that would close a loop — and the number of edges is $V-1$ regardless of which one is grown.

That independence is the first sign that the argument is about the graph rather than about a choice made inside it. Counting the spanning trees of a graph is a substantial question with a beautiful answer, and none of it is needed here: any one will do.

One more property matters and is easy to miss: the tree is maximal in a specific sense. Adding any other edge of the graph to a spanning tree creates exactly one loop, because the two ends of the new edge are already joined by a unique path through the tree. That is the fact the whole argument leans on later — every leftover edge closes a loop in the corner tree, and a loop in the plane is a curve with an inside, which is what gives each leftover edge something to separate.

The leftover edges are a tree of the faces #

Now the step that makes the proof.

Draw a small square in the middle of every face, including the unbounded region outside the whole picture — which is a face, and is the one readers forget. Each edge of the graph separates exactly two faces, so each edge has a natural partner joining those two squares. That partner graph is the dual.

The claim is that the edges not used by the corner tree, read as edges of the dual, form a spanning tree of the faces.

Both halves have to be checked, and both are the same fact seen from two sides.

No loop. Suppose the leftover edges contained a loop in the dual. A closed curve in the plane has an inside and an outside — which is the Jordan curve theorem, and is harder than it looks — so that loop would enclose at least one vertex of the original graph. Any path from that enclosed vertex to a vertex outside must cross the loop, and crossing means using one of the leftover edges. But the corner tree uses no leftover edges, and it reaches every vertex from every other. Contradiction.

Connected. Suppose the leftover edges left two groups of faces unjoined. Then some closed curve separates the two groups without crossing any leftover edge, so it crosses only corner-tree edges — and a curve separating faces while crossing tree edges encircles a loop in the tree. Trees have no loops. Contradiction.

So the leftovers form a tree on $F$ nodes: $F-1$ edges. The corner tree has $V-1$. Nothing else exists.

It is worth checking the count on the picture rather than taking it from the algebra. The cube’s flattening has eight vertices, so the heavy tree has seven edges; it has six faces, counting the region outside the drawing, so the dashed tree has five; and seven and five are twelve, which is the number of edges a cube has. Every edge in the figure is either heavy or faint, and none is both.

Where the argument is spent #

Every proof of Euler’s formula spends a hypothesis somewhere, and locating the spending is the most useful thing a second proof does.

This one spends planarity, twice, and both times in the same sentence: a closed curve in the plane has an inside and an outside. That is what makes “enclose a vertex” mean anything, and it is what makes the two contradictions above contradictions. On a surface with a handle it is false — a loop round a doughnut separates nothing — and there the two trees do not fit together, which is exactly right, because the answer there is not 2.

The deletion proof spends the same hypothesis in a different place: it needs each deletion step to either remove one edge and one face, or one edge and one vertex, and never anything else. On a torus the very first step can remove an edge without merging two faces, because the loop it was part of did not separate anything.

So the two proofs are not independent confirmations. They are two ways of drawing down the same assumption, and it is worth knowing which one, because a formula whose hypothesis is invisible looks like a fact about counting rather than what it is: a fact about surfaces.

The formula does not care what is drawn #

One virtue of the tree argument is how little it uses. It never mentions convexity, or straight edges, or flat faces, or the solid the graph came from. It works on any connected graph drawn in the plane without crossings, however scrawled.

That is worth stating plainly because the formula is usually met attached to polyhedra, and the attachment is historical rather than mathematical. The theorem is about a graph in a plane. Polyhedra come into it because the surface of a convex solid can be flattened into exactly such a graph, and that is the whole of their involvement.

Who found it, and how late #

Euler stated the formula in a letter to Goldbach in 1750 and published it in 1758, and his proof — cutting a solid down by slicing corners off — has a gap in it that took a century to close: it assumes the piece left after each cut is still a polyhedron of the kind the argument applies to.

The argument drawn here is von Staudt’s, from 1847, and it is the first proof of the formula that is correct as written. Karl von Staudt was working on projective geometry and needed the result for something else; the two-tree decomposition is a paragraph in a book about a different subject. It is now the proof most often given in graph theory courses, usually without the name attached.

Between Euler and von Staudt there is a hundred years of proofs that are not quite proofs, and the interesting part is that everyone knew the theorem was true throughout. Legendre gave an argument in 1794 by projecting the solid onto a sphere and adding up spherical areas, which is genuinely correct and which needs the fact that a spherical triangle’s angles exceed a half turn by its area — a heavier tool than the subject deserves. Cauchy gave the flattening argument in 1813, which is the one usually taught and which needs a theorem about planar graphs he did not have.

Lakatos built an entire book, Proofs and Refutations, out of that hundred years, and it is worth reading precisely because the thing being examined is not whether the theorem is true. It is what a theorem’s statement quietly assumes, and how the assumptions get discovered — which is by somebody producing an object that satisfies the words and not the conclusion.

What it costs #

The tree proof is harder to draw than the deletion proof, and that is a real cost on a site that draws things.

The deletion proof is a sequence of pictures each simpler than the last, ending at a single edge, and it can be followed with no vocabulary at all. The tree proof needs the dual graph — an object that has to be constructed and explained before the argument starts — and needs the reader to accept two proofs by contradiction about closed curves. The picture is one frame rather than a sequence, and that frame carries two graphs at once.

What is bought for that price is the number. The deletion proof leaves the reader knowing that the alternating sum is invariant, and knowing its value only because the last picture happened to be a single edge with two ends and one face: $2 - 1 + 1 = 2$. The tree proof produces the two as $1 + 1$, one from each tree, and that decomposition survives generalisation: on a surface of genus $g$, the leftover edges fail to form a tree by exactly $2g$ edges, which is where $\chi = 2 - 2g$ comes from.

Why the theorem has so many proofs #

Euler’s formula is one of the most over-proved statements in mathematics: published arguments run to at least twenty, by induction on faces, by shelling, by spherical area, by discharging, by electrical networks, by binary counting on a shelling order, and by algebraic topology, where it is a triviality about the ranks of three vector spaces.

That abundance is not redundancy. Each proof extends to a different place, and knowing which is which is most of the value.

The deletion proof extends to any planar graph and stops there. The tree proof extends to surfaces, because the failure of the leftovers to be a tree is measurable. Legendre’s spherical-area proof extends to Gauss–Bonnet, where the total curvature of a smooth surface is $2\pi\chi$ and the polyhedral version is the special case where all the curvature is concentrated at the corners. The algebraic proof extends furthest and explains least: it makes $\chi$ an alternating sum of ranks, which generalises to every dimension at once and to spaces no drawing can reach, at the cost of saying nothing whatever about a cube.

So a second proof is not an insurance policy against the first being wrong. It is a different set of hypotheses, and therefore a different generalisation, and the question worth asking of any new proof is not whether it is shorter but what it can be pushed into.

A last remark on the shape of the split, because it explains the asymmetry a reader may have noticed. The corner tree was chosen and the face tree was whatever was left, but the construction could have been run the other way — choose a spanning tree of the faces and the leftovers form a spanning tree of the corners. The two are on exactly equal footing, and the figure could have been drawn with the dashed tree heavy and the heavy one dashed. That symmetry between a planar graph and its dual is a recurring one, and it is the reason the formula treats $V$ and $F$ alike while $E$ sits between them with a minus sign.

What the picture cannot show #

The dashed lines between the small squares are drawn as straight segments between face centres, and one of them runs off to a square that has been placed below the drawing to stand for the outer face. That face is not down there. It is everywhere outside the outer square, extending to infinity in every direction, and it is a single face — the same face on all four sides of the picture.

Every drawing of a planar graph’s dual has this problem, and it is the same problem as drawing a sphere with a point removed: the natural home for these arguments is the sphere, where the outer face is an ordinary face like any other and nothing has to be sent to infinity. On a sphere the picture would be symmetric, the outer face would be no more special than the inner one, and the awkward square below the drawing would be a square like the rest.

The figure also cannot show the two contradictions. Nothing is drawn about the loop that would have to exist, because the whole point is that it does not.

The ladder from here #

Below: the formula itself, with the flattening proof. Above: the angle that is missing at every corner, which is the same number wearing geometry rather than combinatorics, and the solids where the answer is not two, which is where the hypothesis spent above is finally examined.

Sideways, the dual graph is the object a map’s colouring problem is really about, and the same interdigitating-trees picture is the reason a maze drawn from a spanning tree has exactly one route between any two points — with the leftover walls forming the tree of the rooms.

The shape of the argument #

The habit worth taking is the one that made the proof work: split a set into two parts that can each be counted, rather than counting the whole thing.

Nothing above counts edges. It counts two trees, each by the same one-line rule, and then observes that the edges have all been used exactly once. Counting the same thing two ways is the standard move of combinatorics; counting a thing once by splitting it into two easy pieces is the move here, and the pieces were found by asking what the leftovers of a natural construction happen to be.

That question — what is left over, and does it have a structure of its own? — is one of the more productive things to ask of any greedy construction. The leftovers of a spanning tree are a spanning tree of the dual. The leftovers of a matching are an alternating path. The leftovers of the Euclidean algorithm are the next remainder, which is the whole algorithm. In each case what looked like waste was the other half of the object.