---
tag: H5463B2XND
kind: proof
name: Proof of Kőnig's theorem by alternating paths
msc: [05C70]
proves: 0JP0ZF57PN
uses: [07DVHJ8N0A, 0Z87BHAFTB, 0KDADE9RQ8, 0JDE56HWQ8, 0Z49NTR1DZ]
methods: [0J0XBKG64S]
sources:
  - url: https://en.wikipedia.org/wiki/Kőnig's_theorem_(graph_theory)
    locator: Constructive proof without flow concepts
---

## 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|07DVHJ8N0A]] with parts $X$ and $Y$. Let $M$ be a [[matching|0Z87BHAFTB]] and $C$ a [[vertex cover|0KDADE9RQ8]].
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|0JDE56HWQ8]] $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|0Z49NTR1DZ]]. 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$.

## Idea

Starting from the unmatched vertices on one side, follow paths that alternate between non-matching and matching edges. A maximum matching admits no such path to an unmatched vertex, because flipping it would give a bigger matching. Taking the unreached vertices on one side and the reached ones on the other gives a cover with one vertex per matching edge.