Enough partners in every finite group

Hall’s theorem says that a set of applicants can each be given a different post they are qualified for, unless some group of applicants has fewer qualified posts between them than it has members. The condition is obviously necessary — three people cannot share two posts — and the theorem’s content is that it is also sufficient: a shortage in some group is the only thing that can go wrong.

The theorem is about finite graphs, and it is natural to ask whether it survives when the graph is infinite: infinitely many applicants, infinitely many posts, and the condition checked on every finite group. It does not. And the way it fails, and the one repair that brings it back, say something about infinity that is visible in a single picture.

A graph that passes every finite test #

Take applicants $a_0, a_1, a_2, \dots$ and posts $b_1, b_2, b_3, \dots$. Applicant $a_0$ is qualified for every post. Each other applicant $a_i$ is qualified for exactly one, $b_i$.

Hall’s condition holds for every finite group. A finite group of applicants that does not include $a_0$ is some $a_i$’s, each with its own post, so it has exactly as many posts as members. A finite group that includes $a_0$ has infinitely many posts between them, since $a_0$ alone qualifies for all of them. Either way there is no shortage.

There is no matching of all the applicants. Suppose $a_0$ is given some post $b_j$. Then $a_j$, whose only qualification is $b_j$, has nothing. Every choice for $a_0$ strands exactly one other applicant, and not giving $a_0$ anything strands $a_0$.

The obstruction here is not a group with too few posts. Every group has enough. What is wrong is global: the one flexible applicant is needed everywhere at once, and wherever it goes it displaces somebody. The finite theorem’s certificate of failure — a small, checkable set of people short of posts — does not exist.

Where the proof of the finite theorem breaks #

It is worth seeing why the finite proof does not transfer, because the reason predicts the repair.

The finite theorem can be proved by building the matching one applicant at a time, fixing it up with augmenting paths when an applicant cannot be placed. Each fix-up changes the assignments of finitely many people, and after finitely many steps everyone is placed. On an infinite graph the process never finishes, and nothing guarantees that the assignments settle down: a given applicant’s post may be changed infinitely often, and then there is no final matching to point to.

A cleaner way to see the danger is to collect every way of matching the first $k$ applicants — every partial matching — into a tree. The root is the empty matching; the nodes at level $k$ are the matchings of $a_0, \dots, a_{k-1}$; each node’s children extend it by one more applicant. A matching of all the applicants would be an infinite path down this tree, each node extending the one before.

Every branch of this tree dies, and it is worth seeing each death as a small Hall violation arriving late. The branch that gives $a_0$ the post $b_1$ dies immediately, when $a_1$ arrives; the branch that gives it $b_{100}$ lives for a hundred levels and then dies. So the tree has nodes at every level — there are partial matchings of any finite number of applicants — and no infinite path. The tree is infinite in two directions at once: infinitely deep and, at the root, infinitely wide. Each branch’s death is honest — at the moment it dies, some applicant really has no post left — but no single death is the reason the whole tree fails, and that is why no finite witness exists.

A tree with finitely many children at every node #

That combination — every level nonempty, and yet no infinite path — is exactly what König’s lemma says cannot happen in a tree where every node has only finitely many children. Its proof is a greedy walk: at the root, one of the finitely many children has infinitely many descendants, since finitely many finite subtrees would be finite; step to that child and repeat. The walk never gets stuck, and it traces an infinite path.

In the tree of partial matchings the number of children of a node is the number of posts available to the next applicant. If every applicant is qualified for only finitely many posts, the tree is finitely branching, and König’s lemma applies.

The second tree has at most two nodes at each level. Wrong choices die quickly, right ones continue, and because each level is finite the lemma guarantees that some choice at each step leads on for ever. The infinite path it finds is a matching of the whole infinite set of applicants.

Now put the pieces together. Suppose every applicant has finitely many qualifications and Hall’s condition holds for every finite group. Then every finite set of applicants — in particular the first $k$, for each $k$ — can be matched, by the finite theorem, so every level of the tree is nonempty. The tree is finitely branching. By König’s lemma it has an infinite path, and that path is a matching of all the applicants.

Hall’s theorem holds for infinite graphs in which every left vertex has finite degree. Marshall Hall Jr. proved it in 1948, and Richard Rado gave a general form the following year. The counterexample shows the degree condition cannot be dropped: one applicant with infinitely many options is enough to break it.

Why the beginnings do not simply add up #

It might seem that the tree is an unnecessary detour. If the first $k$ applicants can always be matched, for every $k$, why not take a matching of the first ten, extend it to the first twenty, and so on? The trouble is that a matching of the first ten need not extend to any matching of the first twenty. The finite theorem promises a matching of each beginning, but the matchings it promises for different beginnings may disagree about everybody, and there is no guarantee that any of them is the start of a longer one.

The finite-degree tree shows this happening on a small scale. Giving $a_0$ the post $b_1$ is a perfectly good matching of the first applicant, and it cannot be extended even one step, because $a_1$ needs $b_1$. What the tree does is keep every partial matching at once, and König’s lemma picks out a sequence of them that do extend one another — not by constructing it cleverly, but by the counting argument that one of finitely many children must lead on for ever. The finite theorem supplies the raw material, level by level, and the lemma supplies the consistency that the finite theorem alone cannot.

Hilbert’s hotel as a matching #

Infinite matchings behave in ways that finite ones cannot, and the familiar paradox of the infinite hotel is one of them. Take applicants $a_1, a_2, \dots$ and posts $b_1, b_2, \dots$, with $a_i$ qualified for $b_i$ and $b_{i+1}$. Giving every $a_i$ the post $b_i$ matches everyone and uses every post. Giving every $a_i$ the post $b_{i+1}$ also matches everyone — and leaves $b_1$ empty. The same graph has a perfect matching and a matching of the whole left side that misses a post, which in a finite graph with equal sides is impossible.

So in an infinite graph, “every applicant is placed” and “every post is filled” are independent statements, and neither follows from the other even when both sides are the same size. That is why the infinite theory needs two separate conditions to recover a perfect matching, and why the counterexample can fail in one direction while succeeding in the other. In a finite graph the pigeonhole principle ties the two together: a matching that places $n$ applicants in $n$ posts must fill every post, since there is nowhere else for them to go. Infinity breaks exactly that step, and with it the automatic link between the two sides.

Compactness, and what it costs #

The argument is an instance of compactness: a property that holds for every finite part of a structure holds for the whole, provided the parts can only be put together in finitely many ways at each stage. The same principle gives the de Bruijn–Erdős theorem that an infinite map is four-colourable if every finite part is, and it is the reason finite conditions like Hall’s so often suffice for infinite objects with finite local structure.

For countably many applicants, König’s lemma needs no special axioms — each level of the tree is finite and can be searched in order. For uncountably many, the tree is replaced by a product of finite sets, and the argument needs a genuinely infinite principle: that a product of compact spaces is compact, or equivalently some form of the axiom of choice. Rado’s version of the theorem for families of any size is one of the standard places where set theory’s choice principles become visible in combinatorics. The finite theorem needs nothing; the countable one needs a little; the one for arbitrary families needs a principle that cannot be proved from the other axioms of set theory — three statements of the same fact, graded by how much infinity they are allowed to use.

Regular infinite graphs #

One consequence is worth stating separately. A finite bipartite graph in which every vertex has the same degree always has a perfect matching, because the edge count forces Hall’s condition.

The same count works for any finite set of vertices in an infinite graph where every vertex has degree $k$: a set $S$ sends out $k|S|$ edges, each vertex on the other side receives at most $k$ of them, so $S$ has at least $|S|$ neighbours. The degrees are finite, so the infinite theorem applies. The only thing that has to be checked is the degree bound, and here it is built in: every vertex has exactly $k$ neighbours, so every node of the tree of partial matchings has at most $k$ children. Every infinite bipartite graph in which every vertex has the same finite degree has a matching covering each side — for instance, an infinite grid of squares coloured like a chessboard can have its dark squares paired off with neighbouring light ones, with nobody left over. Here a perfect matching can also be written down directly — pair each dark square with the light square to its right — so compactness is not needed; its value is that it gives the same conclusion for every regular graph, including ones with no pattern to follow.

Two one-sided matchings make a perfect one #

There is a second infinite version of Hall’s theorem, and it has no finite counterpart because in the finite case it is trivial.

Suppose there is a matching covering every applicant, and separately a matching covering every post. In a finite graph that already forces the two sides to have the same size, and the first matching is then perfect. In an infinite graph it does not settle anything by itself: the counterexample above has a matching covering every post — give each $b_j$ to $a_j$ — and none covering every applicant, which is the whole trouble. But if both one-sided matchings exist, a perfect matching exists too. The proof is the one that shows two injections make a bijection: overlay the two matchings, and the resulting graph breaks into paths and cycles, each of which can be split into a perfect matching of its own vertices. It is due to Dénes Kőnig, and it is the graph-theoretic form of a lemma Stefan Banach used in 1924 to prove the Cantor–Schröder–Bernstein theorem.

So there are two ways to recover Hall’s theorem for infinite graphs: bound the degrees on one side, or supply matchings from both sides. The counterexample violates both — $a_0$ has infinite degree, and no matching covers every applicant — which is why nothing can be salvaged there.

What the drawings cannot contain #

Every figure is a finite piece of an infinite graph. The counterexample is drawn to $a_6$ and $b_6$, with dots; the trees are drawn to six levels. The claims — Hall’s condition on every finite set, no matching of the whole left side, a tree with no infinite path — are about the infinite objects, and the figures check them only on what is drawn. The arguments in the text are what reach the rest.

The counterexample’s check is on subsets of the drawn vertices. The figure verifies Hall’s condition on all subsets of the first seven applicants, treating $a_0$’s neighbourhood as infinite. For any finite set of applicants in the full graph the same two-case argument applies, and it is short enough that the check is an illustration rather than a proof.

The finite-degree tree is a chosen example. It was built so that wrong choices die one step later and the surviving path is easy to see. In general a finitely branching tree of partial matchings may have many infinite paths or one, and they may be very hard to find; König’s lemma guarantees existence and supplies no algorithm when the tree cannot be searched.

Still open: how hard it is to find the matching #

For countable graphs with finite degrees, a matching of the whole left side exists; but can it be computed? If the graph is presented by a program that lists each applicant’s finitely many qualifications, can a program list the matching? Not always. Alfred Manaster and Joseph Rosenstein showed in 1972 that there are computable graphs of this kind in which every matching is uncomputable — the infinite path through the tree exists but cannot be followed by any algorithm — which places the infinite marriage theorem at a precise level of the hierarchy that reverse mathematics uses to measure the strength of theorems. Which versions of the theorem sit at which level, and exactly how much of König’s lemma each needs, has been worked out for many variants; for matchings with extra conditions, such as stability or maximum weight, the picture is still being filled in.

There is also a quantitative question. For finite graphs, the deficiency version of Hall’s theorem says exactly how many applicants must go without. For infinite graphs a single number cannot say it, and describing the “size” of what a best matching must leave out — in a sense that distinguishes one stranded applicant from infinitely many — needs cardinal arithmetic and is not settled for general graphs.

A single applicant with too many options #

The counterexample is almost comically small: one vertex joined to everything, and a row of vertices with one option each. Nothing about it is exotic. It is the kind of arrangement that arises whenever one resource is universally acceptable and every other is specialised — a single generalist among specialists — and it would be matched without difficulty in any finite version, where the generalist simply takes whatever is left over at the end. In the infinite version there is no end for anything to be left over at. It shows that a condition checked on every finite part can fail to control the whole, and it shows exactly why — the one vertex whose choices cannot be exhausted. Everything else in the infinite theory is the recovery from that example. Bound the choices, and compactness does the rest; the finite theorem, applied to longer and longer beginnings, is stitched into an infinite matching by a lemma about trees.

The finite theorem’s great virtue was that failure always had a small witness — a group short of partners that anyone could check. The infinite counterexample has no witness of that kind, and that is the real lesson. When a condition checked on finite parts fails to decide an infinite question, the thing to look for is not a larger finite part but a place where infinitely many choices are open at once, and a single vertex with infinitely many options is the simplest such place there is.