# Optimal matchings and augmenting paths in finite simple graphs.

Let $G$ be a finite simple graph. A matching $M$ in $G$ is any set of independent edges, we say that $M$ is optimal iff there is no other matching $M^+$ in $G$ with more edges than $M$. Fix $M$, a simple path $p$ in $G$ is called alternating w.r.t. $M$ iff for every adjacent edges $e_{i},e_{i+1}\in p$ it holds $e_{i}\in M, e_{i+1}\not\in M$ or $e_i\not\in M, e_{i+1}\in M$. An alternating path $p=e_1\cdots e_n$ is called augmenting w.r.t. $M$ iff $e_1,e_n\not\in M$ and $e_1,e_n$ are not adjacent to edges in $M\setminus p$.

Ex. from Diestel. Let $G$ be a finite simple graph and let $M$ be a matching in $G$. Then $M$ is optimal if and only if $G$ does not admit any augmenting path $P$ w.r.t. $M$.

Proof. ($\Rightarrow$) If $P$ is an augmenting path w.r.t. $M$, then we can improve $M$ by taking the symmetric difference $M\Delta P$.

($\Leftarrow$) Let $M$ be a sub-optimal matching and let $M^+$ be a matching greater than $M$, i.e. let $|M^+| > |M|$, such that $k:= |V(M^+)\setminus V(M)|$ is minimum possible.

Then, (*) there is no path $P:= v_1e_1\cdots e_{n-1}v_n$ such that $n\geq 3$, $v_1\in V(M^+)\setminus V(M)$$e_{\text{odd}}\in M^+\setminus M, e_{\text{even}}\in M\setminus M^+$, $v_n\in V(M)\setminus V(M^+)$ and $v_i \in V(M^+)\cap V(M)$ for every $1; since otherwise we can argue against $k$ minimality by considering the matching $M^+\Delta P$.

Still $|M^+| > |M|$ imply that there exists $v_1\in V(M^+)\setminus V(M)$. We observe that:

1. There exists $v_2$ s.t. $(v_1, v_2)\in M^+\setminus M$ and w.l.o.g. (otherwise we found an augmenting path) $v_2\in V(M^+)\cap V(M)$.

2. There exists $v_3$ s.t. $(v_2, v_3)\in M\setminus M^+$ and w.l.o.g. (by (*)) $v_3\in V(M^+)\cap V(M)$

3. There exists $v_4$ s.t. $(v_3, v_4)\in M^+\setminus M$.

Now, if $v_4\in V(M^+)\setminus V(M)$, then we found an augmenting path, otherwise it must be $v_4\in V(M^+)\cap V(M)$, but then we are in a configuration similar to 1. and we can iterate 2. and 3. Since $|V|$ is finite there must be an augmenting path $a:=v_1v_2v_3v_4v^{1}_3v^{1}_4v^{m}_3v^{m}_4$ such that $v_1, v^{m}_4\in V(M^+)\setminus V(M)$ and $V(a)\setminus \{v_1, v^{(m)}_4 \}\subseteq V(M^+)\cap V(M)$Q.E.D.