Konig's theorem

**König's theorem:** in every bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. One direction is the weak duality from the previous lesson (cover ≥ matching). The other direction needs a construction of a cover that is no larger than the matching.

Take a maximum matching M. Let Z be the set of vertices reachable from the free left vertices by **alternating paths** (non-matching edges from left to right, matching edges from right to left). Define the cover K = (Left \ Z) ∪ (Right ∩ Z): the left vertices the search did **not** reach, plus the right vertices it did reach. The following three facts prove the theorem.

First, every right vertex in Z is matched, because a free right vertex in Z would end an augmenting path, which cannot exist when M is maximum. Second, each matching edge has exactly one end in K: if its left end is reached, its right end was the way in (so the right end is in K and the left is not); if its left end is not reached, the right end cannot be reached either (it would pull its mate in), so the left end is the only cover vertex. Hence |K| = |M|. Third, K covers every edge: an edge from a reached left vertex always leads to a reached right vertex, so every edge has either an unreached left end or a reached right end.

• Free left vertices are in Z by definition, so they are never in the cover.
• Free right vertices are never in Z, so they are never in the cover either.
• The cover has one vertex for each matching edge: that is why it is minimum.

1// coverL / coverR flag the cover vertices on each side; true when the cover is valid and as large as the matching
2static boolean konigHolds(int[][] edges, boolean[] coverL, boolean[] coverR, int matchingSize) {
3    int size = 0;
4    for (boolean b : coverL) if (b) size++;
5    for (boolean b : coverR) if (b) size++;
6    for (int[] e : edges) if (!coverL[e[0]] && !coverR[e[1]]) return false;   // edge {leftVertex, rightVertex}
7    return size == matchingSize;
8}

The algorithm has three steps after the maximum matching is known. **(1)** Mark every free left vertex as reached and queue it. **(2)** Pop a left vertex u; for each neighbour v that has not been reached, mark v reached and, if v is matched, mark its mate w reached and queue it. **(3)** Output the left vertices that were **not** reached and the right vertices that **were** reached.

The BFS looks at each edge at most once, so the construction costs O(V + E) on top of the matching. Use the animation: the “Workers and jobs” preset has maximum matching 3. The only free left vertex is 3. The search reaches right vertex 0′ from it, steps back along the matching edge to 0′'s mate, left vertex 1, and finds nothing new from there. The reached set is {3, 1} on the left and {0′} on the right, so the cover is the unreached left vertices 0 and 2 plus the reached right vertex 0′: three vertices for a matching of three edges.

Two by-products come for free. The vertices **outside** the cover form a maximum independent set, and the complement of the cover on each side tells you which workers and jobs are in the bottleneck that prevents a perfect matching, the same bottleneck Hall's theorem describes.

1static boolean[][] minVertexCover(int left, int right, List<Integer>[] adj, int[] matchL, int[] matchR) {
2    boolean[] visL = new boolean[left], visR = new boolean[right];
3    Deque<Integer> queue = new ArrayDeque<>();
4    for (int u = 0; u < left; u++) if (matchL[u] == -1) { visL[u] = true; queue.add(u); }   // start at every free left vertex
5    while (!queue.isEmpty()) {
6        int u = queue.poll();
7        for (int v : adj[u]) {                                        // left to right: any edge (the matching edge of u is already visited)
8            if (visR[v]) continue;
9            visR[v] = true;
10            int w = matchR[v];                                        // right to left: only along the matching edge
11            if (w != -1 && !visL[w]) { visL[w] = true; queue.add(w); }
12        }
13    }
14    boolean[] coverL = new boolean[left], coverR = new boolean[right];
15    for (int u = 0; u < left; u++) coverL[u] = !visL[u];              // left vertices the search did NOT reach
16    for (int v = 0; v < right; v++) coverR[v] = visR[v];              // right vertices the search reached
17    return new boolean[][]{coverL, coverR};
18}

1static boolean[][] minVertexCover(int left, int right, List<Integer>[] adj, int[] matchL, int[] matchR) {
2    boolean[] visL = new boolean[left], visR = new boolean[right];
3    Deque<Integer> queue = new ArrayDeque<>();
4    for (int u = 0; u < left; u++) if (matchL[u] == -1) { visL[u] = true; queue.add(u); }   // start at every free left vertex
5    while (!queue.isEmpty()) {
6        int u = queue.poll();
7        for (int v : adj[u]) {                                        // left to right: any edge (the matching edge of u is already visited)
8            if (visR[v]) continue;
9            visR[v] = true;
10            int w = matchR[v];                                        // right to left: only along the matching edge
11            if (w != -1 && !visL[w]) { visL[w] = true; queue.add(w); }
12        }
13    }
14    boolean[] coverL = new boolean[left], coverR = new boolean[right];
15    for (int u = 0; u < left; u++) coverL[u] = !visL[u];              // left vertices the search did NOT reach
16    for (int v = 0; v < right; v++) coverR[v] = visR[v];              // right vertices the search reached
17    return new boolean[][]{coverL, coverR};
18}