Part II · The Classic Theory

Matching, Covering and Packing

Created by Felipe Casadei

Pairing workers with jobs, students with schools, donors with patients: after this chapter you will know exactly when a perfect pairing exists, how to build one step by step, and what the visible obstruction looks like whenever one does not.

Why pairing problems matter

Here is the chapter's opening question. You have a set of workers and a set of jobs. Lines connect each worker to the jobs they can do. Can you assign every worker a different job? In graph language: pick as many edges as possible so that no two picked edges touch the same vertex. Each picked edge marries its two endpoints. Such a set of edges is called a matching.

The first surprise of the chapter is not that matchings can fail to exist. It is that failure always leaves fingerprints. When a full pairing is impossible, the graph contains a small, checkable obstruction that proves it: a group of workers who collectively know too few jobs, or a set of vertices whose removal shatters the graph into too many odd-sized pieces. Theorems of this shape say: either the thing you want exists, or an obvious blocker exists, and never neither. They are called min-max theorems, and this chapter is the place where you meet them for the first time.

The second half of the chapter widens the lens. Matching is a special case of packing: fitting as many disjoint copies of some structure into a graph as possible. Disjoint edges give matchings; disjoint cycles and edge-disjoint spanning trees give the other two packing problems studied here. The natural opposite of packing is covering: using as few vertices or as few trees as possible to touch every structure of a given kind. The two are dual forces. You can never pack more disjoint structures than any cover has elements, because each packed structure uses up at least one cover element. The deep results of this chapter say that in many settings the gap between the best packing and the smallest cover is zero, and in others it is bounded by a formula.

These are not museum pieces. The stable matching algorithm in this chapter runs hospital residency assignment in the United States, and the theory behind kidney exchange programs is the matching theory of general graphs. Network engineers use edge-disjoint spanning trees for routing that survives link failures. Beyond the applications, the chapter teaches a habit of thought: whenever you want something and cannot get it, hunt for the certificate that proves you cannot.

New notation in this chapter

Thirteen symbols are new here. Everything else comes from Chapter 1 and is re-explained briefly where it appears. If set language such as \(S \subseteq A\) ("S is a subset of A") still feels shaky, Chapter 0 is the bootstrap.

Matchings, factors, and the trap of "maximal"

We start with the central definition, then immediately defuse the most common misunderstanding about it.

One warning before anything else. A matching is called maximal if you cannot add one more edge to it. It is called maximum if no matching in the whole graph has more edges. These sound alike and are not the same. Figure 2.1 shows the smallest example: a path on four vertices.

Alternating and augmenting paths

For this section and the next two, our graphs are bipartite: the vertex set splits into two sides \(A\) and \(B\), and every edge runs between the sides, never inside one. Think of \(A\) as workers and \(B\) as jobs. Following Diestel's convention, vertices called \(a, a'\) sit in \(A\) and vertices called \(b, b'\) sit in \(B\).^[1]

Why alternation? Because alternation is exactly the structure you can flip. Along an augmenting path the edges outside \(M\) outnumber the edges inside \(M\) by one. Exchange the two kinds and every interior vertex stays matched (it just changes partners), while the two endpoints go from single to matched. Figure 2.2 shows the whole move.

Augmenting paths are the engine of every practical matching algorithm: repeatedly find one and flip it, and when none exists, stop. The theorems of this chapter explain what the world looks like at that stopping point.

König's theorem: the first min-max tie

What certifies that a matching cannot be improved? Here is the natural upper bound.

Covers bound matchings for free. Each guard can watch at most one matching edge, since matching edges share no vertices. So every cover is at least as large as every matching. The question with content is whether the two meet, and in bipartite graphs the answer is yes.

Proof idea. Take a maximum matching \(M\). From each of its edges choose one endpoint by a rule: choose the \(B\)-side endpoint if some alternating path reaches it, otherwise the \(A\)-side endpoint. That selects \(|M|\) vertices, one per matching edge. Suppose some edge dodged all chosen guards. Following alternating paths to that edge's \(B\)-end, one checks: since \(M\) is maximum, no alternating path can be augmenting, and this forces the \(B\)-end to have been chosen after all, a contradiction. So the chosen \(|M|\) vertices watch every edge, and cover size \(|M|\) meets matching size \(|M|\). The full details are in Diestel §2.1.^[1]

König's theorem is the model min-max theorem. Whether or not your matching is best, a short proof exists either way: exhibit a bigger matching, or exhibit a cover of the same size. This two-sided checkability is the conceptual ancestor of the duality that runs through Chapter 6's flows and much of optimization.

Hall's marriage theorem

König answers "how big is the best matching?" The employment question is more pointed: can every worker be placed? Here is the obvious obstacle. If some group of 5 workers only knows 4 jobs between them, no assignment can place all 5. Hall's theorem says this obvious obstacle is the only one.

Proof idea. Necessity is the paragraph above. For sufficiency, suppose the condition holds but some worker \(a\) stays single under a maximum matching. Gather everything reachable from \(a\) by alternating paths. If any reachable job is unfilled, an augmenting path exists and the matching was not maximum. Otherwise every reachable job is matched back to a reachable worker, which makes the set of reachable workers exactly one larger than the set of reachable jobs. The marriage condition then forces an edge from a reachable worker to a new job, which extends reachability, a contradiction. Diestel gives two further proofs, including a slick one by taking an edge-minimal subgraph satisfying the condition, which turns out to be precisely a matching.^[1]

Hall's theorem has a clean consequence for regular graphs. Recall from Chapter 1 that a graph is \(k\)-regular if every vertex has degree exactly \(k\), meaning \(k\) edges touch it.

Proof idea. Counting edges from each side, \(k|A| = k|B|\), so the sides have equal size. Any group \(S \subseteq A\) sends out exactly \(k|S|\) edges, and all of them land inside \(N(S)\), which can receive at most \(k|N(S)|\) edges in total. So \(k|S| \le k|N(S)|\), Hall's condition holds, and a matching of \(A\), here perfect, exists. This corollary is why a fixture list between two equal leagues, each club drawn against \(k\) opponents from the other league, always splits into \(k\) rounds with every club playing in each.

The same corollary powers a much older theorem, through a trick worth seeing.

Proof idea. A connected \(2k\)-regular graph has an Euler tour, a closed walk using every edge exactly once (Chapter 1). Split each vertex \(v\) into an "out" copy and an "in" copy, and turn each step of the tour into an edge from one vertex's out-copy to the next vertex's in-copy. The result is a \(k\)-regular bipartite graph, which has a perfect matching by the corollary above. Merging the copies back, that matching becomes a subgraph of the original where every vertex has degree exactly 2: a 2-factor. Petersen's original 1891 argument was hard; with bipartite matching machinery it takes three sentences. Recasting a problem into bipartite form is a trick you will see again.

Stable matchings: adding preferences

So far, any job would do. Real people have rankings. What should a good assignment even mean when everyone ranks their options? Maximizing total edges ignores preferences entirely. The right target, discovered by Gale and Shapley, is stability.

Proof idea: run a proposal process. Repeatedly pick an unmatched \(A\)-vertex that some neighbour would still accept (the neighbour prefers that new edge to its current matching edge, if it has one). Add the best such edge from the proposer's point of view, and drop the neighbour's old edge. Watch the \(B\)-side: every change makes some \(B\)-vertex strictly happier, and a given \(B\)-vertex can improve at most once per edge it has, so the process must stop. When it stops, no unmatched \(A\)-vertex is acceptable to any neighbour, and that is exactly stability. The argument is a template for proving that decentralized processes settle down.

Beyond bipartite: Tutte's theorem

Drop the two-sides assumption. When does an arbitrary graph have a perfect matching? Hall's condition no longer even makes sense, so we need a new kind of obstruction. Parity supplies it.

Now delete a set \(S\) of vertices and look at the wreckage \(G - S\), the graph left after removing \(S\) and all edges touching it (Chapter 1 notation). Every odd component of \(G - S\) must send at least one matching edge into \(S\), and each vertex of \(S\) can receive at most one such edge. So if \(G\) has a perfect matching, then \(q(G - S) \le |S|\): the number of odd components left is at most the number of vertices deleted. Tutte's theorem says this is the whole story.

Proof idea. Necessity is the counting above. Sufficiency is genuinely clever: assume \(G\) satisfies the condition but has no perfect matching, and make \(G\) edge-maximal with this property (adding edges never destroys the condition). In such a maximal graph one examines the set of vertices joined to all others. If every component of the rest were a complete graph, a direct pairing would succeed. If some component is not complete, one manufactures two "near-miss" matchings from the maximality and splices them along an alternating walk into a genuine perfect matching, a contradiction. The full construction is in Diestel §2.2, and it rewards a careful read.^[2]

Tutte's theorem has a famous corollary. Recall from Chapter 1 that a graph is cubic if every vertex has degree 3, and that a bridge is an edge whose removal disconnects its component.

Proof idea: verify Tutte's condition by counting. Fix \(S\) and an odd component \(C\) of \(G - S\). The degrees inside \(C\) sum to an odd-ish total that forces an odd number of edges to leave \(C\) toward \(S\); "no bridges" rules out exactly one, so at least 3 edges leave each odd component. That is at least \(3\,q(G-S)\) edges arriving in \(S\), while cubic-ness lets \(S\) absorb at most \(3|S|\). Divide by 3 and Tutte's condition holds. The bridge hypothesis is not decoration, as the next figure shows.

The Gallai–Edmonds structure theorem

Tutte's theorem is a yes/no answer. The Gallai–Edmonds theorem is the anatomy textbook: it describes what every graph, with or without a perfect matching, looks like from a matching's point of view. Its atomic pieces are graphs that just barely miss.

Proof idea. Choose \(S\) to maximize the deficiency \(q(G - T) - |T|\) over all vertex sets \(T\), taking a largest maximizer. Each property then falls out of the maximizing choice: a component that failed to be factor-critical, or a failure of Hall's condition in \(G_S\), would let you enlarge \(S\) or shift a vertex and increase the deficiency, contradicting maximality. Hall's theorem is the engine inside step (i), which is why this chapter proved it first. The bookkeeping around the theorem also shows what every maximum matching of \(G\) must look like: it matches all of \(S\) into distinct components and pairs each component's remainder internally.^[2]

Packing versus covering: the Erdős–Pósa theorem

Time to widen the lens as promised. Fix a class \(\mathcal{H}\) of target shapes, say the class of all cycles. Two rival goals appear. Packing: fit as many vertex-disjoint copies of shapes from \(\mathcal{H}\) into \(G\) as possible. Covering: pick as few vertices as possible so that every copy in \(G\) is touched. Each packed copy eats at least one cover vertex, so a cover is never smaller than a packing. König's theorem said the two are equal when \(\mathcal{H}\) is "a single edge" and the graph is bipartite. For cycles, equality fails, but it fails by a bounded amount, and that is the next theorem.

Proof idea. The quantitative heart is a lemma about cubic multigraphs (multigraphs, from Chapter 1, allow parallel edges and loops): once a cubic multigraph has at least \(s_k\) vertices, where \(s_k\) is about \(4k \log k\), it must contain \(k\) disjoint cycles. The lemma is proved by induction on \(k\): grab a shortest cycle \(C\), which is short because minimum degree 3 forces a short girth (Chapter 1), delete it, tidy the remainder back into cubic form, and apply induction. For the theorem, one takes inside \(G\) a maximal subgraph \(H\) whose degrees are all 2 or 3. Maximality forces every cycle of \(G\) to interact with \(H\), and a case analysis shows each cycle either belongs to a small collectable family or passes through the degree-3 vertices of \(H\), to which the lemma applies. Either the packing or the bounded cover falls out.^[3]

Computer scientists call a vertex set meeting every cycle a feedback vertex set; it is the standard object for breaking circular dependencies, and the Erdős–Pósa theorem guarantees a small one whenever large cycle packings are absent.^[3] The theorem also returns in Chapter 12, where graph-minor theory yields a sweeping generalization.

Tree packing and arboricity

Matching packed disjoint edges; Erdős–Pósa packed disjoint cycles. The third packing problem concerns spanning trees, and here the disjointness moves to the edges. Recall from Chapter 1 that a spanning tree of a connected graph is a subgraph reaching every vertex, connected, with no cycles, and that a spanning tree of an \(n\)-vertex graph always has exactly \(n - 1\) edges. Two spanning trees are edge-disjoint if they share no edges (they necessarily share all vertices). How many edge-disjoint spanning trees fit inside a given graph?

The exact criterion counts edges between districts. Given a partition \(P\) of the vertex set into \(r\) classes (districts), a cross-edge is an edge with its two ends in different classes. Any spanning tree must reconnect the \(r\) districts, and reconnecting \(r\) things needs at least \(r - 1\) connections, so each spanning tree uses at least \(r - 1\) cross-edges. If \(k\) edge-disjoint spanning trees exist, then every partition into \(r\) classes must have at least \(k(r-1)\) cross-edges. That much is forced. What is not obvious is that this requirement is also sufficient.

Proof idea for the corollary: in any partition into \(r\) districts, each district has at least \(2k\) edges leaving it, since deleting those edges would disconnect the graph. Summing over districts counts every cross-edge at most twice, so there are at least \(\tfrac{1}{2} \cdot 2kr = kr \ge k(r-1)\) cross-edges, and the packing theorem applies. Note that plain \(k\)-edge-connectivity is not enough, as Figure 2.11 shows; the doubling is honest.

Covering is the mirror question: how few trees, overlaps now allowed, are needed so that every edge of \(G\) lies on at least one of them? The obstruction is density. Any tree can carry at most \(|U| - 1\) edges inside a vertex set \(U\), so if some \(U\) induces more than \(k(|U|-1)\) edges, \(k\) trees cannot cover them. Recall the notation \(\|G[U]\|\) from Chapter 1: the number of edges of the induced subgraph \(G[U]\), which keeps exactly the edges with both ends in \(U\).

Arboricity is worth remembering as a single number measuring maximum local density: it is small exactly when no group of vertices anywhere in the graph is edge-rich. For \(K^4\): the whole vertex set gives \(\|G[U]\| = 6 \le 2 \times 3\), the condition holds with \(k = 2\), and the two coloured trees of Figure 2.11 achieve the cover, so the arboricity of \(K^4\) is 2 (one tree cannot cover 6 edges with only 3).

Diestel derives both classical theorems from one modern statement that needs no hypotheses at all.

In words: every connected multigraph splits into districts that are individually rich, each holding \(k\) edge-disjoint spanning trees, while the map of districts is globally poor, needing only \(k\) trees to blanket it. Packing succeeds locally exactly where covering succeeds globally. The proof takes \(k\) spanning trees whose union covers as many distinct edges as possible, and studies exchange chains: domino lines of swaps of the form "add this edge to that tree, remove one edge of the cycle it closes" (the cycle in question is the fundamental cycle \(C_e\) from Chapter 1). The key lemma says a duplicated edge that starts an exchange chain is wasted capacity: executing the cascade grows the union, contradicting maximality. The districts are then read off from where exchange chains can start. This exchange argument foreshadows matroid theory, and the theorem's infinite version appears in Chapter 8.^[4]

Path covers and Dilworth's theorem

The chapter closes with directed graphs, where each edge points from one vertex to another (Chapter 1). A directed path is a one-way trail through distinct vertices, each edge pointing forward along it; its last vertex is where it ends, and a single vertex counts as a path of length zero. For a set \(\mathcal{P}\) of such paths, \(\mathrm{ter}(\mathcal{P})\) collects their last vertices.

What limits a path cover from being small? Independent vertices. Recall the independence number \(\alpha(G)\) from Chapter 1: the largest number of vertices no two of which are joined by an edge. A directed path can contain at most one vertex from a set with no edges among its members... almost. A path could revisit the neighbourhood of such a set. The theorem of Gallai and Milgram makes the bound genuine, and sharper than expected.

Proof idea. Among all path covers, take one whose set of last vertices \(\mathrm{ter}(\mathcal{P})\) is minimal: no other path cover's last-vertex set sits properly inside it. Then induct on the number of vertices: delete a last vertex, shorten its path, and re-check minimality in three small cases. The induction is delicate, and what it hands back is a path cover together with an independent set of representatives, one drawn from each path. The theorem simultaneously generalizes König's theorem: orient every edge of a bipartite graph from \(A\) to \(B\), and a minimum path cover is exactly a maximum matching plus leftover lone vertices.^[5]

The most famous consequence lives in order theory. In a partially ordered set \((P, \le)\), such as numbers ordered by divisibility, a chain is a subset whose elements are pairwise comparable, a ladder; an antichain is a subset whose elements are pairwise incomparable, a shelf. An antichain can meet each chain at most once, so covering \(P\) by chains needs at least as many chains as the largest antichain has elements. Dilworth's theorem says this bound is always achieved.

Proof from Gallai–Milgram in three sentences. Build the directed graph on \(P\) with an edge from \(x\) to \(y\) whenever \(x < y\). Directed paths are then exactly chains, and independent sets are exactly antichains. Gallai–Milgram supplies a path cover with one representative per path forming an antichain, so the number of chains used is at most the largest antichain, and the easy direction closes the gap.

Dilworth's theorem earns its keep in scheduling. If tasks are partially ordered by "must finish before", then a chain is a to-do list a single machine can process in order, an antichain is a set of tasks no two of which are sequenced, and the theorem says the minimum number of machines needed equals the largest such set.^[5]

What to carry forward

Four things deserve permanent residence in your head. First, the min-max habit: when an object you want fails to exist, look for the small certificate that proves it, whether a starved group (Hall), an over-shattering vertex set (Tutte), or a cover matching your packing (König, Dilworth). Second, augmenting paths: improvement by rearrangement, not just addition, the engine of matching algorithms. Third, the packing-covering duality, exact in this chapter's best theorems and bounded in Erdős–Pósa's. Fourth, the trick of recasting problems into bipartite form, which turned an 1891 struggle into three lines.

The threads continue. König's theorem reappears in Chapter 3 as the bipartite case of Menger's theorem, and the min-max style matures into the max-flow min-cut duality of Chapter 6. The stable marriage theorem proves Galvin's list-colouring theorem in Chapter 5. The tree packing theorem returns in infinite form in Chapter 8, and the Erdős–Pósa theorem is reborn in Chapter 12 as an early corollary of graph-minor theory.