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<i<n; 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.

augmenting_path