Proof of Kőnig's theorem by alternating paths

Proof

We show that every vertex cover is at least as large as every matching. Then, from a maximum matching, we build a vertex cover of the same size.

Covers are at least as large as matchings.

1. Let $G$ be a finite bipartite graph with parts $X$ and $Y$. Let $M$ be a matching and $C$ a vertex cover.
2. Each edge of $M$ has an end in $C$. A vertex is an end of at most one edge of $M$. So choosing such an end for each edge of $M$ gives an injective map from $M$ to $C$, and $\abs{M} \le \abs{C}$.

A cover from a maximum matching.

3. Fix a matching $M$ with the largest number of edges. A vertex is matched if it is an end of an edge of $M$. Let $U$ be the set of unmatched vertices of $X$.
4. An alternating path is a path $p_0, p_1, \dots, p_k$ with $p_0 \in U$, such that $p_{i-1} p_i \notin M$ for odd $i$ and $p_{i-1} p_i \in M$ for even $i$. As $G$ is bipartite and $p_0 \in X$, $p_i \in X$ exactly when $i$ is even.
5. Let $Z$ be the set of vertices that lie on some alternating path. Let $K = (X \setminus Z) \cup (Y \cap Z)$.
6. No alternating path ends at an unmatched vertex of $Y$. Suppose $p_0, \dots, p_k$ is one, with $p_k \in Y$ unmatched. Then $k$ is odd.
7. Let $P$ be its set of edges, and let $M' = M \mathbin{\triangle} P$ be the symmetric difference. It drops the $(k-1)/2$ edges $p_{i-1}p_i$ with $i$ even and adds the $(k+1)/2$ edges with $i$ odd.
8. The vertices $p_0$ and $p_k$ are unmatched, and the edge of $M$ at an inner vertex $p_j$ lies on the path. So no edge of $M \setminus P$ touches the path. Each $p_j$ is an end of exactly one added edge.
9. Hence $M'$ is a matching with $\abs{M} + 1$ edges. This contradicts the choice of $M$.
10. $K$ is a vertex cover. Let $ab$ be an edge with $a \in X$ and $b \in Y$. If $a \notin Z$, then $a \in K$.
11. Let $a \in Z$, on an alternating path $p_0, \dots, p_j = a$, with $j$ even. If $b$ lies on this path, then $b \in Z$.
12. Otherwise, if $j = 0$, then $a \in U$, so $ab \notin M$. If $j \ge 2$, then the edge of $M$ at $a$ is $p_{j-1}a$, and $b \ne p_{j-1}$, so $ab \notin M$.
13. In both cases $p_0, \dots, p_j, b$ is an alternating path, since its last edge has odd index and is not in $M$. So $b \in Z$, and $b \in K$.
14. Every vertex of $K$ is matched. Vertices of $X \setminus Z$ are matched, because $U \subseteq Z$. A vertex of $Y \cap Z$ lies on an alternating path. Cut the path at this vertex to get an alternating path ending there. By Step 6, the vertex is matched.
15. Each edge of $M$ has at most one end in $K$. Let $ab \in M$ with $a \in X$ and $b \in Y \cap Z$, on an alternating path $p_0, \dots, p_k = b$ with $k$ odd.
16. If $a$ lies on this path, then $a \in Z$. Otherwise the path ends with an edge not in $M$, and $p_0, \dots, p_k, a$ is an alternating path. So $a \in Z$ in both cases.
17. Thus $b \in K$ implies $a \notin K$. Since $K$ is a vertex cover, each edge of $M$ has exactly one end in $K$.
18. Map each vertex of $K$ to the edge of $M$ at it, which exists by Step 14. By Step 17, this map is a bijection from $K$ to $M$. So $\abs{K} = \abs{M}$.

Conclusion.

19. Let $\nu$ be the largest size of a matching and $\tau$ the smallest size of a vertex cover. By Step 2, $\nu \le \tau$.
20. By Steps 10 to 18, there is a vertex cover $K$ with $\abs{K} = \nu$. So $\tau \le \nu$, and $\nu = \tau$.