Matching, augmenting path Lemma

Question

In the context of matching, I am trying to prove the following lemma:

Given a matching $M$ of a graph $G$. If $P$ is an $M$-augmenting path, then $M' = M\Delta P$ is a matching such that $|M'|=|M| +1$.

How would you go about proving this?

Answer 1

Well let's define $x_0x_1\cdots x_{n-1}x_n$ your augmenting path such that $x_i\in V$. By definition of augmenting path $x_0$ and $x_n$ are not touched by $M$ and $x_ix_{i+1}\in M$ iff $x_{i-1}x_{i}\not \in M$ so, the length of the path has to be odd and $|M\cap P|=\frac{|P|-1}{2}.$ So, by taking the symmetric difference, the edges that were on $P\cap M$ are not longer in $M$ and viceversa, so you get $|P\setminus (P\cap M)|=|P|-\frac{|P|-1}{2}=\frac{|P|+1}{2}$ and the edges of $M$ which were not in $P$ still there.
Edit:
$M$ a matching, and $P$ an augmenting path, then for each $0<i<n,$ $x_i\in V$ in the path $P$ defined above is touched by just one edge in $M$. Otherwise, $M$ was not a matching. Also, by definition $x_0$ and $x_n$ are not touched by any edge in $M$. So, you know that $x_ix_{i+1}\in M$ iff $i\equiv 1 \pmod 2$(this is why $|M\cap P|$ has to be odd, otherwise it touches $x_n$)

Now $M = (M\cap P)\cup (M\cap P^c),$( both sets are disjoint i.e., $|M|=|M\cap P|+|M\cap P^c|$) and, by the argument above, edges in $M\cap P^c$ do not touch any $x_i\in P.$
Now $M'=M\Delta P =(M\cup P)\setminus (M\cap P)=(M\cap P^c)\cup (P\cap M^c)$ (so $|M\Delta P|=|M\cap P^c|+|M^c\cap P|$) Now, we know that $x_0x_1,x_{n-1}x_n\in M\Delta P$ so $x_0$ and $x_n$ are touched just once in the matching and $x_ix_{i+1}\in M$ iff $i\equiv 0 \pmod 2.$(which is the negation of the condition before). So $x_i$ is just touched once again, which proves that $M'$ is a marching.

Now, involving the two cardinal equations and the numbers we got in the original post, $|M'|=|M\cap P^c|+|M^c\cap P|=|M|-|M\cap P|+|M^c\cap P|=|M|-\frac{|P|-1}{2}+\frac{|P|+1}{2}=|M|+\frac{|P|+1-(|P|-1)}{2}=|M|+1,$ where $M^c\cap P=P\setminus(P\cap M).$

Hope it's clear now.

See this image, represents $P$ under $M$ and $P$ under $M'$ this gives the intuition of why it is still a matching $\color{red}{\text{red edges}}$ are not in the matching and $\color{blue}{\text{blue edges}}.$ are.