2
$\begingroup$

Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| > |M|$, how can one prove that $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at least $|M'|-|M|$ augmenting paths of $M$? I know that there have to exist some $M$-augmenting paths since $M$ is not a maximum matching, but I don't really know how to prove the above.

$\endgroup$

1 Answer 1

2
$\begingroup$

Proof: We first notice a few things about the graph $G(V(M' \oplus M), M'\oplus M)$:

  1. If there exists a cycle in $G$, it will be of even length. One can easily see this because if it was of odd length, two edges of the same matching would have to be incident to the same vertex which contradicts the definition of a matching. Hence, cycles don't contribute to the difference in edges (remember, $|M'| > |M|$)
  2. There can be paths of even and odd length. The former are not of any interest since they contain the same amount of edges from both matchings, not contributing to the difference. On the other hand, paths of odd length that are $M$-augmenting contain exactly one more edges of $M'$ than of $M$. This is because the paths edges alternate between edges of $M'$ and $M$ (also for the even paths) since no two edges of the same matching can constitute a path (as they don't share common vertices). Moreover, a paths of odd length that is $M'$ augmenting isn't of much interest since it doesn't contribute to the difference in edges.

From (2.) follows that only the $M$-augmenting paths of odd length contribute to the difference $|M'| - |M| > 0$ (those paths can also be of length 1). Since each of those paths extends the matching $M$ by one edge, there must at least exist $|M'| - |M|$ of those $M$-augmenting paths since $|M| + |M'| - |M| = |M'|$. Notice that there can be more than $|M'| - |M|$ augmenting paths of $M$ if $M'$ is not a maximum matching (why?).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.