[proofplan] We prove both implications by comparing [matchings](/page/Matching) through [symmetric difference](/page/Symmetric%20Difference). If an augmenting [path](/page/Path) exists, toggling membership of its edges increases the size of the matching by one. Conversely, if a larger matching $N$ exists, the [graph](/page/Graph) with edge set $M \triangle N$ decomposes into alternating paths and cycles; because $N$ has more edges than $M$, one path component must contain one more $N$-edge than $M$-edge, and this path is augmenting for $M$. [/proofplan] [step:Toggle the edges of an augmenting path to obtain a larger matching] Assume that $P = (v_0,e_1,v_1,\dots,e_k,v_k)$ is an $M$-augmenting path. Define \begin{align*} M' := M \triangle E(P), \end{align*} where $E(P) := \{e_1,\dots,e_k\}$ is the edge set of $P$ and $\triangle$ denotes symmetric difference. Because $P$ alternates between edges outside $M$ and edges in $M$, beginning and ending outside $M$, the number of edges of $P$ outside $M$ is exactly one larger than the number of edges of $P$ inside $M$. Therefore \begin{align*} |M'| = |M| - |M \cap E(P)| + |E(P) \setminus M| = |M| + 1. \end{align*} It remains to verify that $M'$ is a matching. Every vertex not lying on $P$ has the same incident edges from $M'$ as from $M$. The endpoints $v_0$ and $v_k$ are $M$-exposed, so after toggling they are incident to exactly the first and last edges of $P$, respectively. Each internal vertex $v_i$ with $1 \le i \le k-1$ is incident along $P$ to exactly one edge of $M$ and exactly one edge of $E(P)\setminus M$; toggling removes the former and inserts the latter. Since $M$ is a matching, no internal vertex is incident to any other edge of $M$. Thus every vertex is incident to at most one edge of $M'$, so $M'$ is a matching. Hence $M'$ is a matching with $|M'| = |M|+1$, and $M$ is not maximum. [guided] Assume that there is an $M$-augmenting path \begin{align*} P = (v_0,e_1,v_1,\dots,e_k,v_k). \end{align*} The standard operation is to remove from $M$ the edges of $P$ already in $M$, and insert the edges of $P$ not in $M$. Formally, define the toggled edge set \begin{align*} M' := M \triangle E(P), \end{align*} where $E(P) := \{e_1,\dots,e_k\}$ and $\triangle$ denotes symmetric difference. Why does the size increase? Since $P$ begins and ends with edges outside $M$, and the edges alternate between $E \setminus M$ and $M$, the path contains one more non-$M$ edge than $M$ edge. Thus \begin{align*} |E(P)\setminus M| = |M \cap E(P)| + 1. \end{align*} Consequently, the symmetric-difference definition gives \begin{align*} |M'| = |M \setminus E(P)| + |E(P)\setminus M|. \end{align*} Since $M \setminus E(P)$ removes exactly the edges in $M \cap E(P)$ from $M$, this is \begin{align*} |M'| = |M| - |M \cap E(P)| + |E(P)\setminus M|. \end{align*} Using $|E(P)\setminus M| = |M \cap E(P)| + 1$, we obtain \begin{align*} |M'| = |M| + 1. \end{align*} We now check that $M'$ is still a matching. Vertices outside $P$ are unaffected. The endpoints $v_0$ and $v_k$ are $M$-exposed, so they had no incident edge of $M$ before the toggle and gain exactly one incident edge from $P$. For an internal vertex $v_i$ with $1 \le i \le k-1$, the two path edges incident to $v_i$ consist of exactly one edge in $M$ and one edge outside $M$. The toggle removes the incident $M$-edge and inserts the other path edge. Since $M$ is a matching, there cannot be any second edge of $M$ incident to $v_i$ outside the path. Therefore every vertex is incident to at most one edge of $M'$, so $M'$ is a matching. Thus the existence of an $M$-augmenting path produces a matching larger than $M$, namely $M'$, and so $M$ cannot be maximum. [/guided] [/step] [step:Decompose the symmetric difference of two matchings into alternating components] Conversely, assume that $M$ is not maximum. Then there exists a matching $N \subseteq E$ with \begin{align*} |N| > |M|. \end{align*} Define the symmetric-difference subgraph \begin{align*} H := (V, M \triangle N). \end{align*} For 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$. Hence the degree of $v$ in $H$ is at most $2$. Since $G$ is finite, every connected component of $H$ with at least one edge is either a path or a cycle. Moreover, along each such component the edges alternate between $M \setminus N$ and $N \setminus M$, because two consecutive edges cannot both lie in $M$ and cannot both lie in $N$. For a connected component $C$ of $H$, define $m(C)$ to be the number of edges of $C$ belonging to $M$: \begin{align*} m(C) := |E(C) \cap M|. \end{align*} Define $n(C)$ to be the number of edges of $C$ belonging to $N$: \begin{align*} n(C) := |E(C) \cap N|. \end{align*} Summing over all connected components of $H$ gives \begin{align*} \sum_C \bigl(n(C)-m(C)\bigr) = |N|-|M| > 0. \end{align*} Therefore there exists a connected component $C_0$ of $H$ such that \begin{align*} n(C_0) > m(C_0). \end{align*} [/step] [step:Find an alternating path with one more new edge than old edge] The component $C_0$ cannot be a cycle, because an alternating cycle contains equally many edges from $M$ and from $N$. Hence $C_0$ is a path. Let \begin{align*} C_0 = (w_0,f_1,w_1,\dots,f_\ell,w_\ell) \end{align*} be this path. Because the edges of $C_0$ alternate between $M$ and $N$, the inequality $n(C_0)>m(C_0)$ implies that the first and last edges of the path both lie in $N \setminus M$. Indeed, an alternating path has equal numbers of $M$-edges and $N$-edges unless both endpoint edges belong to the same matching; the matching contributing both endpoint edges contributes exactly one more edge. Thus \begin{align*} n(C_0) = m(C_0)+1, \end{align*} and $f_1,f_\ell \in N \setminus M$. We claim that $w_0$ and $w_\ell$ are $M$-exposed. Since $w_0$ has degree $1$ in $H$, the only edge of $M \triangle N$ incident to $w_0$ is $f_1$, and $f_1 \notin M$. If an edge of $M$ were incident to $w_0$, then it could not belong to $N$, because $N$ already contains the incident edge $f_1$ and is a matching. Hence that edge would lie in $M \setminus N \subseteq M \triangle N$, contradicting that $w_0$ has degree $1$ in $H$. Therefore $w_0$ is $M$-exposed. The same argument applied to the terminal vertex $w_\ell$ shows that $w_\ell$ is $M$-exposed. Thus $C_0$ is an $M$-augmenting path in $G$. [guided] We have found a connected component $C_0$ of the symmetric-difference graph $H = (V,M\triangle N)$ for which \begin{align*} n(C_0) > m(C_0), \end{align*} where $n(C_0)=|E(C_0)\cap N|$ and $m(C_0)=|E(C_0)\cap M|$. The purpose of this step is to show that this component is exactly an augmenting path for $M$. First, $C_0$ cannot be a cycle. Along every component of $H$, adjacent edges alternate between $M$ and $N$. On a cycle, alternating edges must come in equal numbers: going around the cycle, each $M$-edge is followed by an $N$-edge and each $N$-edge is followed by an $M$-edge. Therefore a cycle would satisfy \begin{align*} n(C_0)=m(C_0), \end{align*} contrary to the choice of $C_0$. Hence $C_0$ is a path. Write it as \begin{align*} C_0 = (w_0,f_1,w_1,\dots,f_\ell,w_\ell). \end{align*} Now use the inequality $n(C_0)>m(C_0)$. In an alternating path, the two matchings contribute equally many edges unless the first and last edges lie in the same matching. If the first and last edges both lie in $M$, then $M$ contributes one more edge. Since here $N$ contributes more edges, the first edge must satisfy \begin{align*} f_1 \in N \setminus M. \end{align*} The same count forces the last edge to satisfy \begin{align*} f_\ell \in N \setminus M. \end{align*} Then \begin{align*} n(C_0)=m(C_0)+1. \end{align*} It remains to check the endpoint condition in the definition of an augmenting path. We prove that $w_0$ is $M$-exposed. The vertex $w_0$ is an endpoint of the path component $C_0$, so it has degree $1$ in $H$, and the unique incident edge of $H$ at $w_0$ is $f_1$. Since $f_1\in N\setminus M$, this edge is not an $M$-edge. Suppose, for contradiction, that some edge $g\in M$ is incident to $w_0$. Because $N$ is a matching and already contains the edge $f_1$ incident to $w_0$, the edge $g$ cannot lie in $N$. Hence \begin{align*} g \in M\setminus N \subseteq M\triangle N. \end{align*} This would give a second edge of $H$ incident to $w_0$, contradicting that $w_0$ has degree $1$ in the path component. Therefore $w_0$ is $M$-exposed. The same argument at the other endpoint shows that $w_\ell$ is $M$-exposed. The path $C_0$ therefore has $M$-exposed endpoints and alternates between edges outside $M$ and edges in $M$, beginning and ending outside $M$. Thus $C_0$ is an $M$-augmenting path. [/guided] [/step] [step:Conclude the equivalence] We have shown that the existence of an $M$-augmenting path implies that $M$ is not maximum. We have also shown that if $M$ is not maximum, then an $M$-augmenting path exists. Taking contrapositives in the second implication, $M$ is maximum only if no $M$-augmenting path exists. Combining the two implications proves that $M$ is a maximum matching in $G$ if and only if there is no $M$-augmenting path in $G$. [/step]