[proofplan] We prove both directions by comparing matchings through symmetric difference. If an $M$-augmenting path exists, toggling the membership of the path edges in $M$ preserves the matching property and increases the number of edges by one. Conversely, if $M$ is not maximum, choose a larger matching $N$ and examine the graph whose edge set is $M \triangle N$. Its components are alternating paths or alternating cycles; since $N$ has more edges than $M$, one component contains more $N$-edges than $M$-edges, and that component must be an $M$-augmenting path. [/proofplan] [step:Toggle an augmenting path to obtain a larger matching] Assume that $P$ is an $M$-augmenting path. Let $F \subset E$ denote the edge set of $P$, and define \begin{align*} M' := M \triangle F = (M \setminus F) \cup (F \setminus M). \end{align*} We show that $M'$ is a matching. Every vertex not on $P$ has the same incident edges from $M'$ as from $M$. Each internal vertex of $P$ is incident in $P$ to exactly two path edges, one in $M$ and one in $E \setminus M$, so after toggling it is still incident to exactly one edge of $M'$ among the path edges. Since $M$ is a matching, no internal vertex has any other incident edge of $M$ outside $P$. Each endpoint of $P$ is exposed by $M$ and is incident to exactly one path edge, which lies in $E \setminus M$, so after toggling it is incident to exactly one edge of $M'$. Thus no vertex is incident to two distinct edges of $M'$, so $M'$ is a matching. Since the edges of $P$ alternate and begin and end outside $M$, the path contains exactly one more edge from $E \setminus M$ than from $M$. Therefore \begin{align*} |M'| = |M| - |M \cap F| + |F \setminus M| = |M| + 1. \end{align*} Hence $M$ is not a maximum-cardinality matching. [/step] [step:Build the symmetric difference graph from a larger matching] Conversely, assume that $M$ is not a maximum-cardinality matching. Then there exists a matching $N \subset E$ such that $|N| > |M|$. Define the symmetric difference edge set \begin{align*} D := M \triangle N = (M \setminus N) \cup (N \setminus M), \end{align*} and let $H = (V,D)$ be the spanning subgraph of $G$ with edge set $D$. At each vertex $v \in V$, at most one edge of $M$ is incident to $v$, and at most one edge of $N$ is incident to $v$, because both $M$ and $N$ are matchings. Hence the degree of $v$ in $H$ is at most $2$. Therefore every nontrivial connected component of $H$ is either a path or a cycle. Moreover, along any such component, the edges alternate between $M \setminus N$ and $N \setminus M$, since two adjacent edges cannot both lie in $M$ and cannot both lie in $N$. [guided] The reason to introduce $H = (V, M \triangle N)$ is that it isolates exactly the edges on which the two matchings disagree. Define \begin{align*} D := M \triangle N = (M \setminus N) \cup (N \setminus M). \end{align*} Thus an edge of $H$ belongs to exactly one of the two matchings. We first control the shape of the connected components of $H$. Fix a vertex $v \in V$. Since $M$ is a matching, at most one edge of $M$ is incident to $v$. Since $N$ is also a matching, at most one edge of $N$ is incident to $v$. Every edge of $H$ incident to $v$ is an edge from exactly one of these two matchings, so $v$ has degree at most $2$ in $H$. A finite connected graph whose vertices all have degree at most $2$ is either a path, a cycle, or a single isolated vertex. The alternation is forced by the matching condition. If two adjacent edges of a component both belonged to $M$, they would share their common endpoint, contradicting that $M$ is a matching. The same argument excludes two adjacent edges both belonging to $N$. Therefore the nontrivial components of $H$ are alternating paths or alternating cycles, with edge types alternating between $M \setminus N$ and $N \setminus M$. [/guided] [/step] [step:Find a component with more $N$-edges than $M$-edges] Let $\mathcal{C}$ be the finite set of connected components of $H$. For each component $C \in \mathcal{C}$, let $E(C) \subset D$ denote its edge set. Since the components partition $D$, additivity over connected components gives \begin{align*} \sum_{C \in \mathcal{C}} \left(|E(C) \cap N| - |E(C) \cap M|\right) = |D \cap N| - |D \cap M|. \end{align*} By the definition $D = M \triangle N$, we have $D \cap N = N \setminus M$ and $D \cap M = M \setminus N$, so \begin{align*} |D \cap N| - |D \cap M| = |N \setminus M| - |M \setminus N|. \end{align*} Since $M \cap N$ is counted once in both $M$ and $N$, subtracting the common intersection gives \begin{align*} |N \setminus M| - |M \setminus N| = |N| - |M|. \end{align*} The choice of $N$ gives $|N| > |M|$, and therefore \begin{align*} \sum_{C \in \mathcal{C}} \left(|E(C) \cap N| - |E(C) \cap M|\right) > 0. \end{align*} Hence there exists a component $C_0 \in \mathcal{C}$ such that \begin{align*} |E(C_0) \cap N| > |E(C_0) \cap M|. \end{align*} [/step] [step:Show the positive component is an augmenting path] The component $C_0$ cannot be an alternating cycle, because an alternating cycle has the same number of edges from $M$ and from $N$. Therefore $C_0$ is an alternating path. Since it has more edges from $N$ than from $M$, the first and last edges of this path both lie in $N \setminus M$. Let $a,b \in V$ be the endpoints of this path. We show that $a$ and $b$ are exposed by $M$. Consider $a$; the argument for $b$ is identical. The unique edge of $C_0$ incident to $a$ lies in $N \setminus M$. If an edge $e \in M$ were incident to $a$, then $e$ could not equal that $N$-edge, and therefore $e \in M \setminus N \subset D$. Thus $e$ would also be an edge of $H$ incident to $a$, contradicting that $a$ is an endpoint of the path component $C_0$. Hence no edge of $M$ is incident to $a$. Similarly, no edge of $M$ is incident to $b$. Thus $C_0$ is a path whose endpoints are exposed by $M$ and whose edges alternate between $M$ and $E \setminus M$, beginning and ending with edges not in $M$. Therefore $C_0$ is an $M$-augmenting path. This proves that if no $M$-augmenting path exists, then no matching $N$ satisfies $|N| > |M|$, so $M$ has maximum cardinality. [/step]