Lesson 2

Theorem (König — Egerváry, 1931). In any bipartite graph \(G\) the maximum size of a matching equals the minimum size of a vertex cover: \[\alpha'(G)=\beta(G) \ .\]

Proof. We again have a weak duality here: the size of any vertex cover is at least the size of any matching (since from each edge in the matching we must take at least one vertex). Therefore \(\alpha'(G) \le \beta(G)\). To prove equality \(\alpha'(G) = \beta(G)\) it suffices to construct a matching and a vertex cover of the same size. To do this, we transform our bipartite graph into a flow network: direct all edges from the first part to the second, and add a source \(s\) with outgoing edges to all vertices of the first part and a sink \(t\) with incoming edges from all vertices of the second part; set the capacity of all old edges to infinity and the edges connected to \(s\) and \(t\) to one.

Find a maximum flow in the resulting network, and assume, without loss of generality, that it is integral. The edges of the original graph through which the flow goes will give us a matching of the same size in the original graph.

Take a minimum cut \(S\). Its capacity is finite (we can, for instance, just cut off vertex \(s\) and obtain a cut of finite capacity). Therefore, the cut does not intersect any edge of the original graph.

Now consider the set \[C=(V_{1} \setminus S) \sqcup (V_{2} \cap S) \ ,\] that is, the vertices of the left part not in the cut, and the vertices of the right part that are in the cut.

It is clear that the size of \(C\) equals the capacity of the cut: the cut intersects exactly the edges \[\{(s, v) \colon v \in (V_{1} \setminus S)\} \sqcup \{(v,t) \colon v \in (V_{2} \cap S) \} \ .\] It is also clear that \(C\) is a vertex cover (because the cut does not intersect edges of the original graph).◼