Exhibit a maximum matching in the graph below, and use various results that we learned so far to give a short proof that it is a maximum matching.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6

Solution

분홍선 확인

For the given matching $M$, $|M| = 8$.
In $M$, there is no augmenting path.
We will prove that if a matching $M$ has no augmenting path, then $M$ is a maximum matching.

Proof:

1. Define a matching $M$ with no augmenting path.

2. Assume, for contradiction, that $M$ is not a maximum matching.

• That is, there exists a larger matching $M'$ such that $|M'| > |M|$.

3. Consider the symmetric difference $M \triangle M'$.

• The subgraph induced by $M \triangle M'$ consists of disjoint alternating paths and even-length cycles, where edges alternate between $M$ and $M'$.

4. Since $|M'| > |M|$, the symmetric difference must contain at least one augmenting path.

• This augmenting path allows us to increase the size of $M$ by flipping the matched and unmatched edges along this path.

5. However, by definition, there is no augmenting path in $M$.

• This leads to a contradiction.

Conclusion:
Thus, $M$ is a maximum matching.