An infinite tree has an infinite path

Here is a claim that sounds like it needs no proof and does. A tree with infinitely many nodes, in which every node has only finitely many children, contains a path that goes on forever.

The obvious objection is that an infinite tree might be infinite sideways — very many short branches — rather than downwards. That is exactly what the finite-branching condition rules out, and seeing why is the whole content.

The walk #

Call a node good if it has infinitely many descendants.

The root is good, because the whole tree is infinite and every node is a descendant of the root.

Now the step. Suppose a node $v$ is good. It has finitely many children, say $k$ of them, and every one of $v$’s descendants other than $v$ itself lies below one of those $k$ children. If all $k$ children had only finitely many descendants, then $v$ would have finitely many — a finite union of finite sets — which contradicts $v$ being good. So at least one child of $v$ is good.

Step to it. Repeat.

The walk never stops, because a good node always has a good child to step to, so it produces an infinite path. That is the proof, and it is four sentences long.

Where the hypothesis is doing the work #

Read the step again and notice which words are load-bearing.

Finitely many children, and a finite union of finite sets is finite. Both are needed and both fail together if a node is allowed infinitely many children.

The counterexample is easy to picture: a root with one child, one grandchild-chain of length one, a chain of length two, a chain of length three, and so on forever. That tree is infinite — it has infinitely many nodes — every branch is finite, and there is no infinite path. What it does not have is finite branching: the root has infinitely many children.

So the lemma is not about infinitude versus finitude in general. It is about a specific trade: unbounded depth is forced when the width at each step is bounded and the total is infinite. Take away the bound on width and the infinitude can hide sideways.

What the figure actually asserts #

The tree in the figure is drawn to depth four and is therefore finite, which means the picture cannot show an infinite path. It shows the mechanism instead, and the substitution is exact.

Infinitely many descendants becomes has a descendant in the bottom row, computed upwards from the last level. At least one child is good becomes at least one child reaches the bottom, and it is asserted at every level: the figure refuses to draw unless each level contains a node that reaches the bottom, and unless the highlighted walk steps only to such nodes.

Those are the same two facts the proof uses, on a finite instance where they can be checked by counting rather than argued for. What cannot be shown is the passage to infinity, and nothing here pretends to show it. The claim the picture supports is that the step works; that the step can be repeated forever is the part that has to be read.

That second figure names the mistake worth naming. A walk that simply always took the first available child would work here and would not work in general: it can step into a subtree that dies out three levels later, and there is no backing up in an infinite process. The goodness test is not decoration — it is what makes the walk safe forever rather than merely for a while.

Comparing the depths is worth a moment. The deeper tree has fewer survivors at the bottom, not more — most of what it starts dies out — and the walk is still safe. That is the shape of the lemma: it does not claim the tree is fat, or that many paths survive, or that survival is common. It claims exactly one thing, that at least one line goes all the way, and that is the least it could claim while still being useful.

The same lemma with the words changed #

König’s lemma has a twin that looks like a different theorem and is not.

If every finite subset of an infinite collection of constraints can be satisfied, the whole collection can be satisfied.

That is compactness, and it is what makes finite reasoning about infinite objects possible at all.

Why they are the same: build a tree whose nodes at level $n$ are the ways of satisfying the first $n$ constraints, with a node’s children being its extensions to the next constraint. If every finite subset is satisfiable, every level is non-empty, so the tree is infinite. If each constraint has finitely many ways of being met, the tree branches finitely. König’s lemma then gives an infinite path — and an infinite path is a choice satisfying every constraint at once.

The translation goes both ways and is nearly mechanical, which is worth knowing because the two statements are useful in different-looking situations.

Three things it decides #

Colouring an infinite map. If every finite piece of an infinite graph can be coloured with four colours, the whole graph can. Build the tree of partial colourings; each vertex has four choices, so branching is finite; every level is non-empty by hypothesis; take the path. This is the de Bruijn–Erdős theorem, and it means the four-colour theorem — proved for finite maps — extends to infinite ones for free.

Tiling the plane. If a set of tiles can cover every finite square region, it can cover the whole plane. The same argument with partial tilings, and it is the reason the question “do these tiles tile the plane” has the character it does — a set of tiles that fails must fail on some finite square, and there is no way to know in advance how big.

Satisfying infinitely many formulas. If every finite set of a collection of formulas has a model, the collection does. This is the compactness theorem of first-order logic, and it has consequences that are hard to believe on first hearing: there are models of arithmetic containing elements larger than every ordinary whole number, because “$x$ is bigger than 1”, “$x$ is bigger than 2”, and so on, form a collection every finite piece of which is satisfiable.

That last consequence is worth sitting with. It says the axioms of arithmetic, whatever they are, cannot pin down the ordinary whole numbers — there is always a model with extra elements at the end. A theory cannot rule out a structure it cannot describe, and it cannot describe “and nothing else”.

The tree a tableau makes #

The connection to the previous essay’s proof trees is not an analogy; it is the same tree.

A tableau branch is a partial description of a way the assumption could hold. A branch that closes is a description that contradicts itself; a branch that stays open is one that does not. So a tableau is the tree of partial satisfying descriptions, and asking whether any branch survives is asking whether the tree has a path.

In the propositional case that is a finite question, because the tree is finite, and the last essay’s termination argument says why. One step up, with quantifiers, the tree can be infinite: a universal formula may need to be instantiated at a term that has not been invented yet, so a branch can grow forever without closing and without settling anything.

And there König’s lemma is exactly the tool. The tableau’s tree branches finitely — each rule has at most two outcomes — so if it is infinite it has an infinite branch, and an infinite open branch describes a model. That is the completeness proof for first-order logic in one sentence: if the tableau does not close, the branch that survives is the counterexample. The lemma is what turns an unfinished search into a finished object.

The finite version, which is the pigeonhole principle #

Strip the infinity out and the lemma becomes something already in this collection.

A path of length $n$ through a tree of branching $k$ is one of at most $k^n$ possibilities. If a tree has more than $k^n$ nodes at level $n$ it has branching more than $k$; if it has more nodes than there are short paths, some path must be long. That is counting, and it is the pigeonhole principle with paths for pigeons.

The relationship is exact enough to be worth stating: König’s lemma is the pigeonhole principle iterated infinitely often, with the goodness test in place of a counting bound. Both say that a quantity which has to be distributed cannot be distributed thinly forever, and both are the kind of argument that produces an object nobody can point at.

That last property is not incidental. The infinite path exists and the proof gives no way to compute it — at each step it says some child is good without saying which, and deciding which requires knowing something about an infinite subtree. There are trees, computable ones, whose infinite paths are all uncomputable. So the lemma is a genuine existence theorem in the strong sense: what it produces cannot in general be exhibited.

Where it fails, and what that costs #

The failure case is the one named above: infinite branching. It is worth a second look because the drawing cannot show it and the reader has to supply it.

Every figure here has nodes with two or three children, because a picture of a node with infinitely many children is not a picture. So the hypothesis that matters most is exactly the one the drawings cannot fail to satisfy, which is an honest limitation and is stated rather than hidden. The pictures show why the walk is safe given finite branching; that finite branching is required is established by the counterexample tree described earlier, which is easy to specify and impossible to draw.

There is a second, subtler cost. The proof uses, at each step, a choice of one good child among possibly several. Making infinitely many such choices is a use of a weak form of the axiom of choice — dependent choice — and König’s lemma is not provable in the bare axioms without something of that kind. It is a small dependence and it is real, and it is the same dependence the witness function needed for the same reason: turning at each step there is one into there is a sequence.

What the lemma does not give #

Two limits are worth stating before the closing, because both are easy to read past and both change what the result is good for.

It gives no bound. The lemma says a path exists; it says nothing about where it goes, how quickly the surviving branch separates from the dying ones, or how deep the search must go before the answer is visible. In the tiling case that is precisely the sting: a set of tiles that cannot tile the plane must fail on some finite square, and the lemma offers no bound on how large that square is. So the question “do these tiles tile the plane?” has a semi-decision procedure in one direction — search bigger and bigger squares until one fails — and none in the other, because a search that has not failed yet is indistinguishable from one that never will.

It gives no construction. The proof chooses a good child at each step without saying which, and there are computable trees whose infinite paths are none of them computable. That is a theorem rather than a shortcoming of the proof: the object exists and cannot be exhibited, and no better argument will make it exhibitable.

Both limits have the same source. The lemma is a pure existence result, and what it trades away for being so short is any information about the thing it produces. It is worth being clear about that, because “there is an infinite path” sounds constructive in a way it is not, and several of the applications above inherit exactly that character: the four-colouring of the infinite graph exists, and finding it may be impossible.

Why a lemma this small matters #

The result is four sentences and it sits under a surprising amount of the field.

Every argument that says a property of all finite pieces is a property of the whole is this lemma, possibly disguised. That pattern is how infinite objects become tractable: the finite pieces can be checked, enumerated, decided; the whole cannot; and compactness is the bridge that lets a conclusion cross.

It also marks a boundary. Compactness is exactly what fails when the constraints are allowed to have infinitely many options each, and it is what fails in logics stronger than first-order — a language that can say “and only finitely many things” is not compact, and the loss of compactness is the price of that expressive power. Which is the trade this field keeps making and keeps paying for: say more, decide less.

The name is worth a footnote of its own. Dénes König published the lemma in 1927, in a paper about infinite graphs, and it is one of a small family of results — with the pigeonhole principle, with Ramsey’s theorem, with the compactness theorem — that are individually almost content-free and collectively hold up a large part of the subject. What they share is a form: a distribution that cannot be spread thinly forever must concentrate somewhere. The pigeonhole version concentrates two objects into one box; the party of six concentrates three mutual acquaintances out of a colouring; König’s version concentrates an infinite path out of an infinite tree.

None of them is hard. All of them are the step that makes the surrounding argument work, and in every case the surrounding argument is where the difficulty actually lives. That is a reasonable thing to expect of a foundational result and it is not what a reader coming to the subject expects, which is why it is worth saying out loud: the load-bearing lemmas of this field are mostly four sentences long.