= Solution
Let the <bipartite graph> have parts $L,R$. Add a source $s$, a sink $t$, capacity-one edges $s\to u$ for $u\in L$ and $v\to t$ for $v\in R$, and capacity $M=|V|+1$ on each original edge directed $L\to R$. Use the <max-flow min-cut theorem>: maximum flow value equals minimum cut capacity. Also use <Integrality of the Ford-Fulkerson algorithm>: integral capacities admit an integral maximum flow, found by integral <augmenting paths>.
An integral flow selects a <matching in a graph>, because each left and right vertex carries at most one unit. Conversely every matching gives a unit flow along its selected $s\to u\to v\to t$ paths. Hence maximum flow value equals maximum matching cardinality.
A minimum cut has capacity at most $|L|$, whereas crossing even one original edge would cost $M>|L|$. For its source side $Z$, no edge of the original graph runs from $L\cap Z$ to $R\setminus Z$. Therefore
$$
U=(L\setminus Z)\cup(R\cap Z)
$$
is a <vertex cover>, and its cardinality is exactly the cut capacity. Conversely, given any cover $U$, use $Z=\{s\}\cup(L\setminus U)\cup(R\cap U)$. No original edge crosses this cut, because both its endpoints would otherwise be outside the cover; its capacity is $|U|$. Thus minimum cut capacity equals minimum cover size, proving <König's theorem for bipartite matching>:
$$
\boxed{\text{maximum matching size}=\text{minimum vertex-cover size}.}
$$
For the algorithm, repeatedly find <augmenting paths> in the <residual network>, then take $Z$ to be the vertices reachable from $s$. Each integral augmentation increases flow by at least one; the total value is at most $\min(|L|,|R|)$. Each reachability search takes $O(|V|+|E|)$ time, so this procedure takes $O(|V|(|V|+|E|))$ time. The network uses only polynomially many edges and integer capacities, yielding the requested <polynomial-time algorithm> and an explicit cover.
Back to article page
