What the search has when it fails

Finding a large matching is a search, and a search that succeeds has produced its own evidence: here are the pairs, count them, check that no vertex appears twice. Finding a largest one is a different kind of claim. It says that none of the arrangements not tried is better, and there is no obvious way to hand that over.

Hall’s theorem supplied one answer, on one side of the graph: a set of applicants with too few posts between them, which anybody can count. There is a better one, and the improvement is that it is symmetric — it names vertices on both sides, it is exactly the size of the matching rather than merely bounding it, and it costs nothing, because the search that stopped has already built it.

A set of vertices with an end of every edge in it is a cover. The figure’s cover has four vertices and the matching has four edges, and that is not a coincidence of this graph: in a graph with two sides, the smallest cover and the largest matching always have the same size. That is König’s theorem, proved in 1931, four years before Hall’s, and equivalent to it.

The easy half is a bound, and the bound goes the right way #

One direction takes a sentence and is worth having first, because it is the reason the equality is a useful thing to want rather than a curiosity.

Every edge of the matching needs a covered end, and no two edges of a matching share a vertex, so a cover must contain at least one vertex from each — different vertices for different edges. It is the pigeonhole principle once more, with the edges of the matching as the things and the cover’s vertices as the boxes. A cover is therefore never smaller than a matching, in any graph whatever, with no hypothesis about sides.

That inequality is what makes a cover a certificate. Exhibit a matching of four and a cover of four and the two pin each other: nothing can be larger than a cover it fits inside, so four is the maximum; and nothing can be smaller than a matching it has to cover, so four is the minimum. Two numbers, computed by two searches that need not know about each other, and their agreement settles both questions at once.

What is not free is that the agreement ever happens. In general it does not, and the shape of graph on which it fails is the subject of the last part of this essay.

Where the cover comes from #

The cover in the figure was not found by looking for it. It is what an augmenting search leaves behind when it fails, and the construction is three lines.

Recall how a matching is enlarged. An augmenting path begins at an unmatched vertex on the left, alternates between unused and used edges, and ends at an unmatched vertex on the right; flipping every edge along it leaves a matching one larger. A matching with no augmenting path is largest — that is Berge’s lemma, and it is what turns keep improving into a stopping rule rather than a hope.

So run the search and let it fail. Call $Z$ everything it reached, on both sides. Then

$$\text{cover} \;=\; (\text{left side} \setminus Z) \;\cup\; (\text{right side} \cap Z),$$

the left vertices the search could not reach, together with the right vertices it could.

That this is a cover is a short check with two cases. Take any edge, from a left vertex $u$ to a right vertex $v$. If $u$ is unreached, the left half of the set covers it and there is nothing to prove. If $u$ is reached, then the search stood at $u$ and looked along every edge leaving it — so it reached $v$ as well, unless $v$ was already reached, and either way $v$ is in $Z$. The right half covers it.

That its size equals the matching’s is the second check, and it is where the hypothesis about sides is spent. Every right vertex the search reached is matched — an unreached-and-unmatched one would have been the end of an augmenting path, and the search failed — and the partner of each is a left vertex the search then reached. Every left vertex the search did not reach is matched too, since the search starts at every unmatched left vertex. So each vertex of the cover is the end of a distinct matched edge, giving a cover no larger than the matching; with the bound of the section above, the two are equal.

Nothing extra was computed. The set $Z$ is the search’s own record of where it has been, which any implementation is keeping anyway, and the certificate is a subtraction from it.

The cover on a graph that succeeds #

It is worth seeing the equality on a graph with nothing wrong with it, because the certificate is usually introduced as a diagnosis and it is not one. Every graph has a smallest cover and the theorem holds everywhere; what changes is whether the cover is smaller than the left side. When it is not — as here — the matching is complete and the cover is the trivial one.

That also explains a small asymmetry in how the two theorems read. Hall’s condition is a statement one notices only when it is violated, and its certificate exists only for graphs that fail. König’s equality holds always, and the certificate is produced always, whether the news is good or bad.

The two figures bracket what a cover can look like. One is a whole side; the other is two vertices on the far side. Between them the cover is a mixture, and which mixture is decided by where the search ran out — which is to say, by the graph rather than by any choice.

The three numbers, measured #

The middle column is worth dwelling on. It is obtained by brute force — every subset of every vertex, checked for whether it touches every edge, smallest one kept — and that is the only way to know that the set the search produced is the smallest cover rather than merely a cover. The construction proves it is a cover and the counting argument proves nothing smaller exists; the scan is the independent confirmation that both are right, and it is what would catch an error in either.

The third column is Hall’s deficiency and it is a different quantity. It counts on one side only, so it is silent about graphs whose left side is fully matched no matter how badly the right side is served. König’s number is about the graph; Hall’s is about the left side’s prospects. The rows where the third column is zero and the first two are less than the number of edges are exactly the rows where that difference shows.

Five other theorems, and one shape of statement #

The bottleneck essay listed a family of results — Menger’s, Dilworth’s, max-flow min-cut — and said they are equivalent to Hall’s in a few lines each. König’s form is the one that makes the family legible, because it is the smallest statement of the shape they all have:

the largest number of disjoint things equals the smallest number of blocking things.

Menger’s theorem says it with paths and separating vertices. Dilworth’s says it with chains and an antichain. Max-flow min-cut says it with flow and a cut. Each has an easy direction which is the counting argument above — a blocker is needed for each disjoint thing — and a hard direction which is the theorem.

The same shape appears wherever a maximum is pinned by a minimum, including in places with no graph in them at all: a lottery over whole assignments is a statement that one polytope’s corners are the other’s, and stable matching is the one member of the family whose min–max is about nobody wanting to defect rather than about a count.

What the easy direction buys is that the hard one becomes checkable. Without the equality, a claim of maximality is unfalsifiable in practice: a referee can only re-run the search. With it, the referee is handed an object of the same size and checks a property of it. That is the whole of what Edmonds meant by a good characterisation, and König’s theorem is the smallest example of one.

The connection to the two numbers a linear program forces to meet is exact rather than analogical. Write the matching problem as a maximisation over variables that are $0$ or $1$ on each edge, and its dual is a minimisation over variables on the vertices — which is the cover, with the integrality dropped. Weak duality is this essay’s one-sentence bound. Strong duality gives an equality between the two fractional problems. What König’s theorem adds, and what linear programming does not supply, is that both optima are reached at whole numbers, and the reason for that sits in the next section rather than in the duality.

The one shape where it is false #

Take away the sides and the theorem goes. A cycle of five has a matching of two and needs a cover of three, and no argument rescues the difference, because there is nothing wrong with the drawing.

The reason is a parity. In a cycle of $2k+1$ edges, any matching leaves at least one vertex out — pairs cannot exhaust an odd number — so it holds at most $k$. Any cover must take at least $k+1$, because the $2k+1$ edges of the cycle need covering and each vertex covers two. The gap is exactly one and it appears in every odd cycle.

A graph with two sides has no odd cycle, which is the only thing this essay’s hypothesis was ever used for. It is the same parity that makes a walk over the bridges impossible decidable by counting alone: a closed walk’s crossings have to balance, and a count that cannot balance forbids the walk. Walk round any cycle of such a graph and each step crosses from one side to the other, so a cycle that returns must have crossed an even number of times. That single fact is doing all the work: the alternating search’s case analysis used it, the cover’s size used it, and the duality’s integrality uses it too — a bipartite graph’s edge-vertex matrix has every square submatrix of determinant $0$ or $\pm 1$, and that is exactly what makes the fractional corners whole.

So all four statements — no odd cycle, König’s equality, the search’s certificate, the whole corners — are one property looked at from four directions. The odd cycle is not a technicality that happens to break a proof. It is the property, absent.

The cycle that stops a search, and the trick that gets past it #

The failure is not only in the theorem. It is in the method, and it is why matching in a graph without sides was open for thirty years after the bipartite case was routine.

An alternating search keeps two kinds of edge in mind and walks between them. Entering an odd cycle, it can leave the cycle only by the vertex it came in at, and to leave it must use an edge of the kind it arrived on — which is not allowed. Every route is blocked and none of the blockages is real: the graph often does have an augmenting path, reachable by entering the cycle on one side and leaving on the other, which no alternating walk can describe.

Edmonds’ answer in 1965 was to contract the cycle to a single vertex and search again. A cycle of odd length with all but one of its vertices matched inside itself — a blossom — has the property that contracting it changes neither the size of a largest matching nor whether an augmenting path exists, so the answer found upstairs unpacks to an answer downstairs. The figure measures exactly that: the contracted graph’s matching plus the two edges hidden inside the cycle is a largest matching of the original, and both were found without reference to the other.

The whole apparatus is there to handle odd cycles, and it is the same odd cycle König’s theorem breaks on. The paper that introduced it is the one that introduced polynomial time as a standard, and the two ideas arrived together because the second was invented to say what the first had achieved.

And the certificate changes shape with the algorithm. In a graph with no sides the right statement is not about covers at all — it is about how many vertices a largest matching misses, counted in odd pieces, and that is what a parity counts when a shortage cannot.

What a cover is for when nobody wants a matching #

The minimum vertex cover is a famous problem in its own right and its fame is entirely about general graphs, which is worth stating because this essay has made it look easy.

The bipartite construction is also the standard tool for completing an array one row at a time, which is how a Latin rectangle is extended without ever completing one by hand.

On a graph with two sides, finding a smallest cover is as cheap as finding a matching — run the search, take the set difference — and that is one of the very few natural problems whose easy cases are delimited so sharply. On a general graph the same problem is NP-hard, and it was one of Karp’s original twenty-one. The difference between the two is the odd cycle and nothing else.

Two consequences follow, and they point in opposite directions. The first is that a great many practical instances are bipartite by construction — jobs and workers, rows and columns, terms and documents — and for those the hard problem is not hard. The second is that an easy problem with a hard general case attracts a standard move: cover the general graph with bipartite pieces, solve each, and accept an approximation. The simplest version of that is to take a maximal matching and use both ends of every edge, which is a cover at most twice the size of the smallest, and after fifty years nobody has a general method that beats the factor of two by any fixed amount.

It is unusual to be able to say where a boundary is with this precision. A property visible in a drawing — no cycle of odd length — separates a problem solved by an undergraduate exercise from one nobody expects to solve at all.

Five vertices a side is the wrong size #

Five vertices a side is small enough to check by eye, which is the wrong size. The theorem’s value appears when the graph is too large for a person to see either number, and every figure here is small enough that a reader can verify the answer without the theorem. What a small drawing shows is the mechanism; the necessity of the mechanism is a different claim and is not drawn.

The cover’s minimality is established by exhaustion and only at these sizes. The table’s middle column scans every subset of the vertices, which is fine at ten and impossible at fifty. The construction’s proof of minimality is the counting argument in prose, and the scan checks the construction rather than replacing it.

The search is drawn as a result and not as a process. One figure marks what the search reached; none of them shows it reaching. An alternating walk is a sequence of decisions, and a still picture of it is the set of places it ended up — which is, as it happens, precisely the object the certificate is made from, so the omission costs less here than it usually does.

And the failure at the odd cycle is drawn once. One graph is exhibited where the two numbers differ by one. That they differ by one in every odd cycle is arithmetic in the prose; that a graph without odd cycles never has them differ is the theorem, and a figure showing four graphs where they agree is evidence for it rather than a proof of it.

Still open here: how much a cover can be trusted #

The equality of this essay is exact and its certificate is free, and both properties evaporate one step outside. On a general graph the two numbers differ, the difference is not bounded by anything simple, and the smallest cover cannot be computed at all at scale. What replaces it is a bound rather than an equality — a cover at most twice the minimum, obtained in one pass — and the question of whether any constant better than two is available has been open since the 1970s, with evidence pointing at no.

The other direction is to keep the exactness and give up on covers. A matching’s shortfall in a general graph does have an exact min–max description; it is counted in odd components rather than in vertices, and finding it is where the sides turn out to have been doing all the work.

A search that leaves a reason #

The habit worth taking from this is about what a failed search should be made to produce.

A search that stops and reports nothing better exists has said something it cannot support. A search that stops and reports here is a set of four vertices covering every edge has said the same thing in a form anybody can check in a minute, and the second report was already inside the first — the set of places the search had been is the certificate, one subtraction away.

So the question to ask of any exhaustive method is what its final state is a proof of. Often the answer is nothing, and the method is a black box whose word must be taken. Sometimes, as here, the wreckage is the theorem, and then a method and a proof are the same object described twice.