A spanning tree for every graph

The choice inside a countable union found the axiom of choice hiding in a two-line proof about countable sets, and measured how much of it the proof uses. This essay goes the other way: it takes a theorem that seems to be about something entirely concrete — graphs — and shows that, for infinite graphs, it is not merely helped by the axiom of choice but equivalent to it. Proving that every connected graph has a spanning tree takes the whole axiom, and the whole axiom follows from it.

A spanning tree of a connected graph is a set of its edges that reaches every point and contains no loop. For finite graphs it is the object behind cheapest networks, behind each user paying for its own last link, behind the count of sixteen trees on four points; every connected finite graph has one, and finding one is easy. The interest is entirely in what “easy” becomes when the graph is infinite, and in why the answer depends on how infinite.

The greedy pass #

The finite proof is a procedure. List the edges in any order. Go through the list and keep each edge unless it would close a loop with edges already kept. At the end, the kept edges form a forest — no loops, by construction — and the forest reaches every point, because if two points were in different pieces of the forest, some path joining them in the graph would contain an edge between two pieces, and that edge closes no loop, so it would have been kept. A forest that joins every point is a spanning tree.

Two things about the procedure matter later, and both are easy to overlook because the finite case hides them. It needs a list of the edges and nothing else: no decision is made that the list does not dictate. And the result depends on the list. The procedure is Kruskal’s algorithm with every edge given equal cost, and different lists give different trees, which is why the cheapest network of each user pays for its own last link is found by listing the edges cheapest first.

Spanning trees are the maximal forests #

There is a second, static description of the same objects, and it is the one that survives into the infinite case.

Order the forests of a graph by inclusion: one forest is below another if all its edges are edges of the other. A maximal forest is one with nothing above it — one to which no edge can be added without closing a loop. In a connected graph the maximal forests are exactly the spanning trees: a forest that misses some point, or falls into two pieces, can always be extended by an edge between pieces, and a spanning tree cannot be extended, since any extra edge closes a loop with the path the tree already contains. The figure checks this on the square with a diagonal, where exhaustion finds 24 forests and 8 maximal ones, matching the eight spanning trees that a determinant that counts trees would count.

So “every connected graph has a spanning tree” can be restated as “the forests of every connected graph have a maximal element”. Stated that way, it is an instance of a general principle about ordered sets — and the general principle is where the axiom of choice lives.

Zorn’s lemma #

A partially ordered set is one in which some pairs of elements are comparable and others may not be. A chain is a family of elements any two of which are comparable — a rising sequence, or a rising family indexed by something larger than a sequence. Zorn’s lemma says: if every chain in a partially ordered set has an upper bound in the set, then the set has a maximal element. The choice nobody can write down drew it on a finite lattice, where it is obvious, and noted that for infinite orders it is equivalent to the axiom of choice.

For forests the hypothesis is easy to check, and the next figure checks it on the infinite square grid.

Take any chain of forests and form the union of all of them. A loop in the union uses finitely many edges; each lies in some forest of the chain; the chain is ordered, so all of them lie in the largest of those finitely many forests; and that forest would then contain the loop, which it does not. So the union is a forest, and it lies above every member of the chain. Every chain has an upper bound, Zorn’s lemma applies, and a maximal forest exists. In a connected graph it is a spanning tree.

The argument is three lines, and the one essential fact in it is that a loop is finite. That fact is what makes the union of a chain of forests a forest, and it is the graph-theoretic version of the compactness that an infinite tree has an infinite path used. Zorn’s lemma supplies everything else: in particular, it supplies the guarantee that the process of adding edges, continued as long as possible, actually ends at something maximal rather than climbing forever.

Listable graphs need no choice #

For a graph whose edges can be listed — any countable graph given with a listing — the greedy pass works exactly as in the finite case, and needs no axiom.

Run the pass along an infinite list $e_1, e_2, e_3, \dots$: keep $e_n$ unless it closes a loop with the kept edges among $e_1, \dots, e_{n-1}$. Every finite stage is a forest; the union of all stages is a forest, by the finiteness of loops; and it spans the graph, by the same argument as before, applied to the stage at which a connecting edge was examined. No choice is made beyond the list itself, and the list was given. For the infinite grid, rows-first and columns-first listings give a comb and its transpose; a shuffled listing gives something irregular. Each is a legitimate spanning tree built by a rule, and none of the three is better than the others; which tree appears is an artefact of the listing, just as which representative appears in a choice is an artefact of the choice function.

So the axiom of choice enters only for graphs too large to list — graphs with uncountably many edges, or countable graphs whose countability is claimed without a listing being provided, as in the countable union. For those, the greedy pass would have to continue past the end of every countable list, through stages indexed by ordinals, choosing at each stage which edge to examine next; the choice nobody can write down described exactly this climb through the ordinals, and Zorn’s lemma is the packaged form of it.

From trees back to choice #

The surprising half of the theorem is the converse. Stephan Höft and Paul Howard showed in 1973 that if every connected graph has a spanning tree, then the axiom of choice holds.

The idea is to build, from any family of non-empty sets, a connected graph in which a spanning tree encodes a choice function. Make a point for each set in the family, and a separate point for each pair consisting of a set and one of its members, so that sets sharing a member do not share a point. Join each pair-point to the point of its own set, and add one extra point joined to every pair-point. The graph is connected. Now take any spanning tree and follow, from each set-point, the unique path in the tree to the extra point. Its first step leaves the set-point, and a set-point is joined only to its own pair-points, so the first step selects one member of the set — exactly one, because a tree contains exactly one path between any two points. Reading off those first steps gives a choice function for the whole family.

So the two statements are equivalent: every connected graph has a spanning tree if and only if every family of non-empty sets has a choice function. A theorem that looks as concrete as anything in combinatorics turns out to carry the whole weight of the most debated axiom in set theory.

The climb through the ordinals, made explicit #

Zorn’s lemma is the tidy form of a procedure that can be described directly, and seeing the procedure explains why it needs choice. By the well-ordering theorem — another of the equivalents of the axiom — the edges of any graph can be arranged in a well-order: a sequence indexed by ordinals, in which every non-empty collection of edges has a first member. Run the greedy pass along that sequence. At each successor stage examine the next edge and keep it if it closes no loop; at each limit stage, such as the stage after all the finitely-indexed edges, take the union of everything kept so far, which is a forest by the finiteness of loops; and continue until every edge has been examined.

The result is a spanning tree, by the same argument as in the finite case, and the procedure has made no arbitrary decisions after the first: the well-order dictates everything. All the choice is concentrated in the well-order itself. For a countable graph with a listing, the listing is a well-order of length $\omega$, and nothing is needed; for an uncountable graph, a well-order of the edges is exactly what cannot be produced without the axiom. Reached from below or not at all described the ordinals such a climb passes through, including the first uncountable one, which no countable sequence of steps reaches.

So Zorn’s lemma, the well-ordering theorem and the greedy pass are one argument in three costumes. The lemma hides the climb, the well-order makes it explicit, and the greedy pass is what the climb does at each step.

A connected graph with no spanning tree #

The converse has a vivid consequence in worlds where the axiom of choice fails. In a world with countably many pairs of socks and no way of choosing one from each pair — the world the choice inside a countable union described — build Höft and Howard’s graph from the pairs: a point for each pair, a point for each sock, each sock joined to its pair and every sock joined to one extra point. The graph is connected; any two points are joined by a path of at most four edges through the extra point. And it has no spanning tree, because a spanning tree would choose a sock from every pair.

That is worth pausing on. The graph is countable in the sense that it is a countable union of finite pieces; it is connected in the most elementary way, every point within four steps of every other; and the greedy pass, which needs only a list of the edges, cannot be run because no list of the socks exists. The obstacle is not the size of the graph but the absence of any way to tell its pieces apart. It is the same obstacle that stopped the countable union, reappearing in graph theory as a connected graph that cannot be pruned to a tree.

Six faces of one axiom #

The spanning-tree theorem joins a list of statements equivalent to the axiom of choice, and the list is the best evidence that the axiom is not a technicality.

Each of the six is the axiom of choice in the language of a different subject. In set theory it is a choice function; in the theory of orders, Zorn’s lemma and the well-ordering theorem; in graph theory, spanning trees; in linear algebra, bases, which a function that adds and is nowhere a line used to build a wild solution of Cauchy’s equation, and which Andreas Blass proved in 1984 to be equivalent to choice; in topology, the compactness of products, shown equivalent by John Kelley in 1950. Mathematicians in each of those subjects use their own version daily, usually without thinking of it as an axiom at all.

The equivalences are also a warning. Anyone tempted to reject the axiom of choice as a set-theoretic indulgence must also give up spanning trees for infinite graphs, bases for infinite-dimensional spaces and compactness of infinite products — each of which is used, in some form, throughout analysis and algebra. Most mathematicians accept the axiom for exactly that reason: its consequences in their own subjects are too useful and too natural to forgo.

They are also invisible in a precise sense. No basis of the real numbers as a vector space over the rationals has ever been written down, and none can be: Robert Solovay built in 1970 a model of set theory, with dependent choice still available for everyday analysis, in which every set of real numbers is Lebesgue measurable — and a basis of that kind would yield a set that is not. The same holds for the spanning trees of large graphs. The axiom supplies them; it never supplies a description of one, and any description at all would be a construction that some model of the remaining axioms rules out. What choice adds is existence without witness, which is exactly what the finite greedy pass never needed.

What the drawings settle and what they do not #

Every figure here is finite or shows a finite piece of something infinite, and on finite graphs nothing needs choosing: the greedy pass, run on a list, settles every case drawn. The poset figure is exhaustive, listing all twenty-four forests and checking that the maximal ones are exactly the trees; the chain figure checks that each stage, and the union of the stages drawn, has no loop. None of this touches the axiom of choice, which concerns graphs no picture can contain.

The Höft–Howard construction is described in outline rather than drawn, because its force lies in an arbitrary family of arbitrary sets; a drawing of three sets with a few elements each would be a finite case, where choice functions exist trivially. And the list of equivalences states results proved elsewhere: the figure lays them out, it does not prove them. The same is true of the graph built from socks. It can be described exactly, and every finite part of it has spanning trees in abundance; what it lacks is a spanning tree of the whole, and the reason is a property of the world of sets it lives in, not of any piece of it that could be drawn. A picture of it would draw the socks in places, and placing them is already the choice that world forbids.

Still open: how much choice for which graphs #

The equivalence is for all connected graphs. For restricted classes the strength drops, and the exact strength is known only in some cases. For countable graphs given without a listing, spanning trees need some countable choice. For graphs of bounded degree, locally finite graphs, connected graphs whose components are finite, and other natural classes, the existence of spanning trees is equivalent to various weak choice principles, and the catalogue of which weak principle matches which class of graphs is incomplete; several cases are settled only in one direction.

Related existence statements behave similarly and are less understood. That every graph has a maximal independent set is equivalent to choice; that every graph has a proper colouring with a given number of colours whenever every finite subgraph does — the de Bruijn–Erdős theorem — needs only a weak form, the Boolean prime ideal theorem, and is known not to need the full axiom. Where between these the existence of perfect matchings, Hamiltonian paths in infinite graphs or other structures lies is answered for some and open for others, and the answers depend delicately on what “infinite” is allowed to mean.

The finite loop #

The spanning-tree theorem for infinite graphs rests on two facts, one combinatorial and one set-theoretic. The combinatorial fact is that a loop is finite, so a growing family of forests never acquires a loop in the limit. The set-theoretic fact is that growing families have limits that can be continued from, which for countable graphs is just a list and for arbitrary graphs is the axiom of choice.

What Höft and Howard showed is that the set-theoretic fact cannot be avoided: there is no cleverer argument for spanning trees that gets by with less. A greedy algorithm that every student can run by hand, extended to graphs too large to list, becomes the axiom of choice itself — which is perhaps the clearest way to see that the axiom is not an exotic assumption but the infinite form of a procedure everybody already trusts.