$\nu(G) \leq \tau(G)$. For any matching $M$ and vertex cover $S$: each edge of $M$ has at least one endpoint in $S$, and these endpoints are distinct (since $M$ is a matching). So $|M| \leq |S|$, hence $\nu \leq \tau$.

$\nu(G) \geq \tau(G)$. We construct a vertex cover of size $\nu(G)$ from a maximum matching $M$.

Let $M$ be a maximum matching. Define $U = \{x \in X : x \text{ is not saturated by } M\}$ (unmatched vertices on the left). Let $Z$ be the set of all vertices reachable from $U$ by alternating paths (paths that alternate between non-matching and matching edges).

Define: $L = Z \cap X$ (reachable left vertices), $R = Z \cap Y$ (reachable right vertices).

Claim: $S = (X \setminus L) \cup R$ is a minimum vertex cover.

$S$ is a vertex cover. Consider any edge $xy$ with $x \in X, y \in Y$:

• If $x \notin L$ (i.e., $x \in X \setminus L$): $x \in S$, so the edge is covered.
• If $x \in L$: $x$ is reachable from $U$ by an alternating path. If $xy \notin M$: the path to $x$ extended by $xy$ reaches $y$, so $y \in R \subseteq S$. If $xy \in M$: $x$ is matched to $y$. Since $x \in L$ is reachable, and $x \notin U$ (matched vertices are not in $U$), $x$ was reached via some $y' \in R$ with $xy' \notin M$, then $y'x' \in M$... Actually, the alternating path to $x$ ends with a matching edge into $x$, meaning the previous vertex $y'$ is in $R$, and $y'x \in M$. But $x$ is matched to $y$ by $M$, so $y' = y$, giving $y \in R \subseteq S$.

$|S| = |M|$. Each matching edge contributes exactly one vertex to $S$: if $xy \in M$ with $x \in L, y \in R$: $y \in S$ (and $x \notin X\setminus L$). If $x \notin L, y \notin R$: $x \in S$ (and $y \notin R$). We cannot have $x \in L, y \notin R$: since $x$ is matched and reachable, the alternating path goes $\cdots \to y' \to x$ (with $y'x \in M$, so $y' = y$), meaning $y \in R$, contradiction. We cannot have $x \notin L, y \in R$: $y$ reachable means an alternating path reaches $y$ via a non-matching edge from some $x' \in L$, then if $yx'' \in M$ the path continues to $x''$, so $x'' \in L$. Since $y$ is matched to $x$ in $M$, $x = x'' \in L$, contradiction.

So each matching edge has exactly one endpoint in $S$, and no vertex of $S$ is unmatched (unmatched vertices in $X$ are in $U \subseteq L$, hence not in $X \setminus L$; unmatched vertices in $Y$ are not reachable, hence not in $R$). Thus $|S| = |M| = \nu(G)$. $\square$