The piece that cannot pair off

Hall’s theorem and König’s are both about a graph with two sides, and both of their obstructions are shortages. Hall’s is a set of applicants with too few posts between them; König’s is a set of vertices small enough to cover everything. Each says a matching fails because something ran out.

Delete the sides and the failures stop looking like that.

That graph has no shortage anywhere. Every vertex has two or three neighbours, every set of vertices has at least as many neighbours as members, and a matching still misses two of the ten. The reason is visible only after something is removed: deleting one vertex leaves three pieces of odd size, each of which can pair up internally except for one leftover, and one deleted vertex can absorb only one of the three leftovers.

Odd is the whole of it #

The argument for why that is an obstruction is short and is worth having before the theorem, because the theorem is its converse and the converse is the hard half.

Take any set $S$ of vertices and delete it. What is left falls into pieces. A piece with an odd number of vertices cannot be perfectly matched inside itself, whatever its shape — pairs use two at a time and an odd count does not divide — so each odd piece contributes at least one vertex that must be matched out of its piece. That is the pigeonhole argument stated about parity instead of about capacity — the leftover exists because a count cannot divide, not because a pool ran dry. The only place out is $S$, since the pieces are not joined to each other.

So if there are $q$ odd pieces and $|S|$ deleted vertices, at least $q - |S|$ vertices go unmatched. Maximise over every $S$ and that is a lower bound on how many a matching misses.

Berge’s theorem is that the bound is exact. The number of vertices a largest matching leaves out is

$$\max_{S} \big(\,\text{odd}(G - S) - |S|\,\big),$$

and nothing else ever gets in the way. Tutte’s theorem of 1947 is the case where the maximum is zero: a graph has a perfect matching exactly when deleting any set leaves no more odd pieces than the set had vertices. Berge’s sharpening came in 1958 and is the form worth carrying, for the same reason the deficiency form of Hall’s is: it says how much is missing rather than merely that something is.

Four vertices, three edges, and the whole mechanism. The centre can pair with one leaf and the other two leaves have nobody at all — not because they are short of neighbours in any counting sense, but because their only neighbour has been used.

Where the empty set is already the answer #

The maximum is over every set including the empty one, and the empty set is often where it sits. A graph with an odd number of vertices has an odd component before anything is deleted, so its formula already returns at least one, which is the obvious statement that an odd number of things cannot pair off.

That is worth stating explicitly because it is the case the picture makes least visible. The formula looks as though it is about surgery; a third of the time it is about nothing more than the parity of the vertex count, and the surgery is what finds the other two thirds.

The control matters more here than in most of these essays, because the formula’s value is a maximum over $2^n$ sets and a maximum is a claim about all of them. A graph on which the answer is zero is a graph where every one of the sixty-four subsets was checked and none produced an excess — which is what a theorem of this shape has to be tested against, since a formula that can only find obstructions and never declare their absence is not a formula at all.

The two numbers, measured against each other #

The point of computing both sides by exhaustion is that neither number is allowed to know the other. A search for a matching reports a count and no reason; a scan over deleted sets reports a reason and a count; the theorem is the claim that the counts coincide, and the table is the place where that claim is exposed to a way of failing.

And the witness column is the interesting one. Two rows show a dash, meaning the empty set was enough — those are the graphs whose vertex count is odd. Two show a single vertex, and those are the graphs where the obstruction genuinely required an incision. The distinction is invisible in the numbers and is the whole difference between a parity accident and a structural one.

Why a shortage cannot see this #

It is worth being precise about how badly Hall’s condition fails to apply here, because the obvious repair is to try it anyway.

Hall’s condition asks whether every set of vertices has at least as many neighbours as it has members. In the hero figure, every set does. In the four-vertex star, the set of three leaves has exactly one neighbour between them — three members, one neighbour — so a naive reading does report trouble there. But the reading is meaningless, because in a graph without sides a vertex is its own neighbour’s neighbour, and the condition as stated is not even well posed: the three leaves are not competing for the centre in the way three applicants compete for one post, since the centre is a vertex of the same kind they are.

What breaks is more specific than that. The bipartite argument works by finding, in a failed search, a set on one side and its neighbourhood on the other, and the two sides are what keep those disjoint. With no sides they overlap, the counting argument’s “different vertices for different edges” stops being available, and the alternating search itself walks into an odd cycle and stops with a blockage that is not a real one.

So the right question is not what a set’s neighbours are but what is left when the set is gone, and the quantity that answers it is a count of pieces rather than of vertices. That is a change of instrument and not a refinement of one.

The pieces that are almost perfectly matched #

There is a structure underneath Berge’s formula that explains why the answer comes out so clean, and it deserves a paragraph because it is what the theorem is really about.

Call a connected graph factor-critical if deleting any one of its vertices leaves a graph with a perfect matching. A single vertex is factor-critical trivially; a triangle is, and so is any odd cycle; a pair of vertices joined by an edge is not, since deleting one leaves an unmatchable single vertex. Factor-critical graphs necessarily have an odd number of vertices, and they are exactly the pieces that appear in the optimal $S$’s components.

The Gallai–Edmonds decomposition makes this exact. Every graph splits into three parts: the vertices missed by some largest matching, the vertices adjacent to those, and everything else. The first part’s components are all factor-critical; the second is the deleted set $S$ that achieves the maximum; and the third has a perfect matching of its own. Every largest matching of the whole graph is then a perfect matching of the third part, a matching of $S$ into distinct odd components, and a near-perfect matching inside each component.

That is why the shortfall is a subtraction. Each odd component loses one vertex unless $S$ rescues it, and $S$ can rescue as many as it has members. Nothing else is happening, and the formula is the accounting of that sentence.

What the theorem buys, in one line, for cubic graphs #

The first real consequence of Tutte’s condition is a statement made sixty years before it, and it is the cleanest demonstration of what a min–max theorem is for: a whole class of graphs cleared in a paragraph of counting.

Every cubic graph with no bridge has a perfect matching. Cubic means every vertex has exactly three edges; a bridge is an edge whose removal disconnects the graph. Petersen proved it in 1891 by an argument nobody found easy; with Tutte’s condition it is arithmetic.

Delete a set $S$ and count the edges leaving one odd component $C$. Adding up the degrees inside $C$ gives $3|C|$, which is odd, and twice the number of edges with both ends in $C$ is even — so the number of edges from $C$ to $S$ is odd. It is therefore at least one, and it cannot be exactly one, because a single edge joining $C$ to the rest would be a bridge. So it is at least three. Now count the edges between $S$ and the odd components in two ways: there are at least $3q$ of them by the last sentence, and at most $3|S|$ of them because each vertex of $S$ has three edges in total. Hence $3q \le 3|S|$, so $q \le |S|$, and Tutte’s condition holds for every $S$ at once.

That is the entire proof. Nothing was constructed, nothing was searched, and no graph was examined; a degree count and a parity are enough to settle infinitely many graphs, because the condition being checked is a condition about every deletion and the count did not care which deletion it was.

It is worth noticing what the bridge hypothesis is doing, since it is the only place the argument could fail. Without it, the edge count from an odd component can be one, and then $q$ can exceed $|S|$ — which is exactly the four-vertex star above, inflated: three odd pieces joined to one vertex by one edge each. The Petersen graph itself, which is cubic and bridgeless, has perfect matchings and is the standard example for the sharper questions about how many.

The odd cycle again, from the other side #

The picture is the same one the cover essay ends on, and the two readings of it are the two halves of this subject.

There, the odd cycle was the reason a min–max equality failed. Here it is the reason an algorithm fails, and the two failures are the same object: an odd cycle with all but one of its vertices matched inside itself is a piece that cannot pair off, and a search that enters it is a search that has found an odd component without knowing it.

Edmonds’ contraction is the repair on the algorithmic side, and the theorem’s odd components are the repair on the structural side. That they are the same repair is not obvious from either statement, and it is the reason the 1965 paper that gave one also settled the other, in the same pass that made a good characterisation a thing anybody had a name for: a contracted blossom is a factor-critical piece treated as a single vertex, and unpacking it is the near-perfect matching inside the piece.

A graph with two sides has neither problem, and that is the whole of what the two theorems above were assuming without saying. Hall’s condition is not a weaker theorem than Tutte’s; it is Tutte’s theorem in the one setting where every component of every deleted set’s remainder can be paired off from one side, so the odd count never arises.

The count that decides a molecule #

The theorem has an application older than itself, and it is a good example of a piece of combinatorics being used before it was proved.

A carbon skeleton drawn as a graph and a perfect matching of it drawn as a choice of double bonds is the Kekulé structure of a molecule, and whether a given skeleton admits one at all is exactly Tutte’s question. The count of distinct perfect matchings — the Kekulé count — was used by chemists from the 1930s as a stability index, and the graphs where none exists are the ones where the drawing rules break down and something else has to be said about the bonding.

Two things about that use are worth keeping. First, the obstruction found in practice is nearly always the odd one: a fragment with an odd number of carbons attached to the rest at one atom, which is precisely this essay’s picture. Second, the count is a much harder quantity than the existence. Deciding whether a perfect matching exists is fast in every graph; counting how many there are is hard in general and was proved so in 1979, though it is computable for planar graphs by a determinant — which is the same gap between is there one and how many that counting spanning trees sits on the easy side of.

Where the exhaustion stops being possible #

Every maximum here is over a set of subsets, and every one of those maxima was found by exhaustion. The count is $2^{n}$, which is the same exponential the deficiency scan runs, and it is run here for the same reason: to obtain the witness by a route the matching search cannot have influenced. That is exactly right at ten vertices and impossible at forty, and no figure on this page indicates the difference. The theorem’s content is that the maximum exists and is achieved by a set one can be handed; how to find that set without trying all of them is a separate question, answered by the Gallai–Edmonds decomposition and not drawn here.

The factor-critical pieces are described and not exhibited. The hero’s three triangles are factor-critical, and the figure does not say so or show the near-perfect matchings inside them that make it true. What the figure shows is the count of odd pieces, which is the number in the formula rather than the structure underneath it.

And no drawing shows a matching being largest. Each thick set of edges is a largest matching because an exhaustive search said so, and a reader looking at the picture sees a matching that happens to be the one drawn. The number beside it is the claim; the drawing is an instance of it.

Still open here: what an obstruction costs to find #

Berge’s formula gives an exact shortfall and a witness, and both are computable in polynomial time by the decomposition the last sections named — so unlike most min–max theorems in this area, this one has no complexity gap hiding in it at all.

Where the questions remain is one step sideways. Counting the matchings rather than finding one is hard, and the planar determinant that evades it does not extend. Matching with weights on the edges is solvable and the algorithm is substantial. And a three-way version — partition the vertices into triples rather than pairs — is NP-complete even on graphs with every degree four, so the whole clean theory of this essay stops the moment the number two is replaced by three. Why two should be so much easier than three is not a question with a short answer, and the parity argument that runs through everything above is the first place to look: a count of pairs has a remainder and a count of triples has two, and nothing in the argument above survives a second one.

The counting question is where the gap is starkest. Counting proper colourings is hard for the same reason counting matchings is, and both sit beside decision problems that are easy — which is the standing pattern rather than an accident of these two. Why two should be so much easier than three is not a question with a short answer, and the parity argument that runs through everything above is the first place to look.

When a shortage is not the shortage #

The lesson is about which quantity to count when a construction fails.

Two theorems above found their obstruction by counting neighbours, and it was the right count because the sides made it right. The moment the sides went, the same count kept returning answers and they stopped meaning anything — which is the more dangerous failure, since a quantity that becomes meaningless usually keeps looking like a quantity.

What replaced it counts something a size cannot see: whether a piece has an odd number of things in it. A piece of size fifteen and a piece of size sixteen are almost the same object and behave completely differently here, and no measurement of how large, how connected or how well-supplied either one is would tell them apart.

So when a count stops explaining the failures, the thing to look for is not a bigger count. It is a different kind of quantity — and parity is the one that most often turns out to have been doing the work, because it is invisible to every measurement of size.