---
title: "Kőnig's Theorem and Minimum Covers"
summary: One alternating DFS gives the minimum vertex cover, the maximum independent set, and — with a small twist — the minimum path cover of a DAG.
difficulty: hard
tags: [matching, duality, cover]
prereq: [matching/bipartite, flow/mincut-models]
see: [matching/applications, flow/mincut-models]
---

## Kőnig's theorem

:::theorem title="Kőnig (1931)"
In a bipartite graph the maximum matching size equals the minimum vertex cover size.
:::

:::proof
Let $M$ be a maximum matching. Run the alternating DFS from all **free left** vertices along edges $\notin M$ and back along edges $\in M$; let $Z_L, Z_R$ be the left/right vertices reached. Claim $C = (L \setminus Z_L) \cup (R \cap Z_R)$ is a vertex cover of size $|M|$.

*Covers every edge.* An edge $uv$ with $u \in L \setminus C$ means $u \in Z_L$; if also $v \notin C$ then $v \in R \setminus Z_R$. If $uv \notin M$, then $v$ would have been reached from $u$ (the DFS follows all non-matching edges out of a reached left vertex) — contradiction. If $uv \in M$, then $u$ is matched, and a matched left vertex is reached only through its matching edge from the right, so $v \in Z_R$ — contradiction. Hence every edge is covered.

*Size.* Each $v \in R \cap Z_R$ is matched (a free right vertex would end an augmenting path, impossible for maximum $M$), so $|R \cap Z_R| \le |M|$, and each $u \in L \setminus Z_L$ that matters is matched to a right vertex in $Z_R$... precisely: no two vertices of $C$ are matched to each other (if $uv \in M$, $u \in Z_L$ or $v \in Z_R$, never both directions), so $|C| \le |M|$; combined with $|C| \ge |M|$ (any cover exceeds any matching, @matching/intro) gives equality. ∎
:::

## Extracting the cover

```cpp konig.cpp
// after any bipartite matching (mt[] on the right side), build the cover:
vector<int> zl(n), zr(m);                    // reached sets
queue<int> q;
for (int u = 0; u < n; u++) if (free_left(u)) { zl[u] = 1; q.push(u); }
while (q.size()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) if (mt[v] != u && !zr[v]) {          // non-matching edge L -> R
        zr[v] = 1;
        if (mt[v] != -1 && !zl[mt[v]]) { zl[mt[v]] = 1; q.push(mt[v]); }  // matching edge R -> L
    }
}
vector<int> cover;
for (int u = 0; u < n; u++) if (!zl[u]) cover.push_back(u);       // L \ Z_L
for (int v = 0; v < m; v++) if (zr[v]) cover.push_back(n + v);   // R ∩ Z_R
```

## Consequences

:::props title="Consequences, each a one-line reduction"
- **maximum independent set** $= V \setminus$ minimum cover, so its size is $n - |M|$ and it is *computable*, not just bounded — "choose the most cells with no two attacking" (@matching/applications),
- **minimum edge cover** (uncovered-vertex-free set of edges): $n - |M|$ for graphs without isolated vertices — take the matching plus one edge per unmatched vertex,
- **Dilworth's theorem**: in a poset, the maximum antichain size = minimum number of chains covering the set. Build the bipartite graph with an edge $x \to y$ when $x < y$; a matching of size $k$ gives a chain cover of size $n - k$, and Kőnig's cover gives an antichain of the same size — this is the algorithm for "longest non-decreasing subsequence"-family problems,
- **minimum path cover in a DAG** (vertex-disjoint directed paths covering all vertices): split each $v$ into $v_{out}, v_{in}$, add $u_{out} \to v_{in}$ for each DAG edge, and the answer is $n - |\text{matching}|$ (@matching/applications),
- **maximum bipartite induced matching / "2D domino placement"**: several of these reduce to matching on a *derived* graph, where the same cover argument certifies optimality.
:::

## The min-cut view

:::note title="The min-cut view (why the same formula appears in @flow/mincut-models)"
With unit capacities on $s \to L$ and $R \to t$ and $\infty$ on the middle edges, every finite cut is: drop a left vertex (pay 1) or drop a right vertex (pay 1) so that no $\infty$ edge survives — i.e. a vertex cover. So the min cut **is** the min cover, and "max matching = min cover" is a special case of max-flow min-cut. The alternating DFS above is what a max flow's final residual graph *is*: $Z_L$ = left vertices still reachable from $s$.
:::

## Output-size traps

:::warning title="Output-size traps"
- If the problem asks for the cover, you must **run the reachability on the final matching** — using the matching mid-loop gives a set that is not a cover,
- Isolated vertices: they are never in $Z_R$ but they are in $L \setminus Z_L$ only if free... an isolated left vertex is free, hence in $Z_L$, hence not in the cover — correct; but for a *maximum independent set* they must be included, and they are (complement of cover), so check your sample with an isolated vertex, which is exactly where off-by-one covers die,
- For "minimum number of rooks/queens covering all marked cells" (the classic), remember it is a cover on the *bipartite row–column* graph, so the answer is $|M|$, not $n - |M|$ — the complement only gives the *largest non-attacking placement*, which is the *other* question people ask.
:::

:::problems
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | extend it: also print a minimum set of students+parents that "touches" every acceptable pair
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | easy | on a tree the cover dual is the same DP with a second state — derive it and check it matches the matching size
:::