[proofplan] Choose a maximum matching $M$ and explore the graph by alternating paths starting at the $M$-exposed vertices of $X$. Let $S \subset X$ and $T \subset Y$ be the vertices reached on the two sides. Maximality of $M$ prevents the search from reaching an exposed vertex of $Y$, so the set $C = (X \setminus S) \cup T$ has exactly one endpoint of each edge of $M$. We prove that $C$ covers every edge, count $|C| = |M|$, and then use the elementary inequality that every vertex cover has size at least every matching. [/proofplan] [step:Choose a maximum matching and define the alternating reachable sets] Let $M \subset E$ be a matching of maximum cardinality. A vertex $v \in X \cup Y$ is called $M$-saturated if it is incident to an edge of $M$, and $M$-exposed otherwise. Define an $M$-alternating path from $X$ to be a finite path \begin{align*} P = (v_0, v_1, \dots, v_k) \end{align*} such that $v_0 \in X$ is $M$-exposed, the vertices $v_0,\dots,v_k$ are distinct, and the edges of $P$ alternate between edges outside $M$ and edges inside $M$, beginning with an edge outside $M$ when $k \ge 1$. Thus, for $1 \le i \le k$, the edge $\{v_{i-1},v_i\}$ lies outside $M$ when $i$ is odd and lies inside $M$ when $i$ is even. Let $Z \subset X \cup Y$ be the set of all vertices reachable by such an $M$-alternating path. Define \begin{align*} S &:= Z \cap X, & T &:= Z \cap Y. \end{align*} [/step] [step:Use maximality of the matching to exclude exposed reached vertices in $Y$] No vertex of $T$ is $M$-exposed. Indeed, suppose that $y \in T$ is $M$-exposed. By the definition of $T$, there is an $M$-alternating path \begin{align*} P = (v_0, v_1, \dots, v_k) \end{align*} from an $M$-exposed vertex $v_0 \in X$ to $v_k = y$. Since $G$ is bipartite with parts $X$ and $Y$, and since $v_0 \in X$ while $y \in Y$, the length $k$ is odd. Hence the first and last edges of $P$ are outside $M$, and the edges of $P$ alternate outside $M$, inside $M$, outside $M$, and so on. Define \begin{align*} M' := M \triangle \{\{v_{i-1},v_i\} : 1 \le i \le k\}, \end{align*} where $\triangle$ denotes symmetric difference. Along the path $P$, the set $M'$ removes the $M$-edges of $P$ and adds the non-$M$ edges of $P$. Since the endpoints $v_0$ and $y$ are $M$-exposed and the path alternates, every internal vertex of $P$ is incident to exactly one edge of $M'$ on the path, and vertices outside $P$ keep their old matching incidences. Thus $M'$ is a matching. The path contains one more non-$M$ edge than $M$-edge, so \begin{align*} |M'| = |M| + 1. \end{align*} This contradicts the maximality of $M$. Therefore every vertex of $T$ is $M$-saturated. [guided] The purpose of this step is to record exactly where maximality of $M$ is used. If the alternating search ever reached an exposed vertex on the $Y$ side, the path from an exposed vertex of $X$ to that exposed vertex of $Y$ would be an augmenting path. Let $y \in T$. By definition of $T$, there is an $M$-alternating path \begin{align*} P = (v_0, v_1, \dots, v_k) \end{align*} with $v_0 \in X$ exposed by $M$ and $v_k = y$. Suppose, for contradiction, that $y$ is also exposed by $M$. Because $G$ is bipartite and $v_0 \in X$, $v_k = y \in Y$, the path has odd length. Since the alternating rule begins with an edge outside $M$, the edges of $P$ have the pattern \begin{align*} E(P) \setminus M,\quad E(P) \cap M,\quad E(P) \setminus M,\quad E(P) \cap M,\quad \dots,\quad E(P) \setminus M. \end{align*} Thus there is one more edge outside $M$ on $P$ than there is edge inside $M$ on $P$. Now define a new edge set \begin{align*} M' := M \triangle \{\{v_{i-1},v_i\} : 1 \le i \le k\}. \end{align*} This operation flips the matching status of every edge of the path: matched edges on $P$ are deleted, and unmatched edges on $P$ are inserted. The endpoints $v_0$ and $y$ were exposed before the flip, so each becomes incident to exactly one inserted edge. Every internal vertex of $P$ was incident along $P$ to one deleted matched edge and one inserted unmatched edge, so it remains incident to exactly one matching edge. Vertices not on $P$ are unaffected. Therefore $M'$ is a matching. Because the path has one more inserted edge than deleted edge, we obtain \begin{align*} |M'| = |M| + 1. \end{align*} This contradicts the choice of $M$ as a maximum matching. Hence no vertex of $T$ can be exposed by $M$. [/guided] [/step] [step:Construct the candidate cover from unreached vertices in $X$ and reached vertices in $Y$] Define \begin{align*} C := (X \setminus S) \cup T. \end{align*} We prove that $C$ is a vertex cover of $G$. Let $\{x,y\} \in E$ with $x \in X$ and $y \in Y$. If $x \notin S$, then $x \in X \setminus S \subset C$, so the edge is covered. It remains to consider the case $x \in S$. Choose an $M$-alternating path from an exposed vertex of $X$ to $x$. If $\{x,y\} \notin M$, appending the edge $\{x,y\}$ to that path gives an $M$-alternating path reaching $y$, so $y \in T \subset C$. If $\{x,y\} \in M$, then $x$ cannot be an exposed starting vertex. Hence the alternating path reaching $x$ has positive even length and its final edge is the unique edge of $M$ incident to $x$. Since $\{x,y\} \in M$ is also incident to $x$, uniqueness in the matching gives that the final predecessor of $x$ is $y$. Thus $y$ is reached, so $y \in T \subset C$. In every case, at least one endpoint of $\{x,y\}$ lies in $C$. Therefore $C$ is a vertex cover. [/step] [step:Count the vertices of the cover by matched edges] We show that $|C| = |M|$ by associating the vertices in $C$ with distinct edges of $M$. First, every $y \in T$ is $M$-saturated by the previous step. Let $m_T(y) \in X$ denote the unique vertex such that $\{m_T(y),y\} \in M$. The alternating path that reaches $y$ ends with a non-$M$ edge unless it has length zero, which is impossible because $y \in Y$. Since $y$ is matched, the search rule follows the matched edge from $y$ back to $m_T(y)$, so $m_T(y) \in S$. Thus every vertex of $T$ is matched by $M$ to a vertex of $S$. Second, every $x \in X \setminus S$ is $M$-saturated. If such an $x$ were exposed, then the path of length zero starting at $x$ would show $x \in S$, a contradiction. Let $m_X(x) \in Y$ denote the unique vertex such that $\{x,m_X(x)\} \in M$. If $m_X(x) \in T$, then following the matched edge from $m_X(x)$ would reach $x$, contradicting $x \notin S$. Hence $m_X(x) \in Y \setminus T$. Therefore the matching edges incident to $T$ are exactly matched edges between $S$ and $T$, while the matching edges incident to $X \setminus S$ are exactly matched edges between $X \setminus S$ and $Y \setminus T$. These two classes are disjoint, and together they contain one distinct edge of $M$ for each vertex of $(X \setminus S) \cup T$. Consequently \begin{align*} |C| = |X \setminus S| + |T| = |M|. \end{align*} [/step] [step:Compare every matching with every vertex cover to prove minimality] Let $N \subset E$ be any matching, and let $D \subset X \cup Y$ be any vertex cover. Since $D$ covers every edge of $N$, each edge of $N$ has at least one endpoint in $D$. Since the edges of $N$ are pairwise vertex-disjoint, distinct edges of $N$ require distinct vertices of $D$. Hence \begin{align*} |N| \le |D|. \end{align*} Taking $N = M$ and $D$ arbitrary gives $|M| \le \tau(G)$. Since the set $C$ constructed above is a vertex cover and satisfies $|C| = |M|$, we also have $\tau(G) \le |C| = |M|$. Therefore \begin{align*} \nu(G) = |M| = \tau(G). \end{align*} This proves the theorem. [/step]