TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 36

Let $M$ be a matching of a simple and undirected graph $G=(V,W)$. An open path $W$ in $G$ is called alternating if exactly every other edge of $W$ is in $M$ . We call an alternating path extending if the start as well as the end vertex of $W$ is not incident with any $e\in M$ . Prove: If $W$ is an extending alternating path, then $M\mathrm{△}W:=(M\setminus W)\cup (W\setminus M)$ is a matching and $|M\mathrm{△}W|=|M|+1$.

Solution

We know that every other edge of $W$ is in $M$. Both end points of the alternating path $W$ are nor incident with any edge of the matching. This means that $W$ starts and ends with an edge, which does not belong to the matching $M$. The number of edges in $W$ must be odd, since otherwise $W$ would not start and end with an edge not belonging to $M$. From this follows that the number of edges in $W$ which do not belong to $M$ has to be one greater than the number of edges belonging to $M$. If we now switch the designation of each edge in $W$ then consequently the number of edges in the new matching (|M ⧍ W|) has to be one larger than the number of edges not belonging to the matching (= number of edges belonging to the old matching $M$).