Show konig thm implies Hall’s thm

교수님께서 몇번 강조를 하셔서 증명은 해봤는데, 2024 기준 시험이나 퀴즈에 출제된 바는 없습니다.

Solution

1. Hall's Theorem:
   For a bipartite graph $G = (X, Y, E)$, a perfect matching exists if and only if the following condition holds:
   $$
   \forall S \subseteq X, |N(S)| \geq |S|.
   $$

2. We need to show that $\alpha'(G) = \beta(G)$ for every bipartite $G$ implies Hall's theorem.

Proof:

1. Suppose the graph $G$ satisfies the condition of Hall's theorem, but there is no perfect matching.

2. By König's theorem, $\alpha'(G) = \beta(G)$. Let $U$ be the minimum vertex cover of $G$, so $|U| = \beta(G)$.

3. Assume $|U| < |X|$. Write $U = X' \cup Y'$, where $X' \subseteq X$ and $Y' \subseteq Y$.
   $$
   |X'| + |Y'| = |U|.
   $$

4. Since $|U| < |X|$, we have:
   $$
   |Y'| < |X| - |X'| = |X \setminus X'|. \tag{1}
   $$

5. Since $U = X' \cup Y'$, there is no edge between $X \setminus X'$ and $Y \setminus Y'$. Thus, $N(X \setminus X')$ exists only in $Y'$.

   • Therefore:
     $$
     |N(X \setminus X')| \leq |Y'|.
     $$

6. By (1), we have:
   $$
   |N(X \setminus X')| \leq |Y'| < |X \setminus X'|.
   $$

7. This violates Hall's theorem because $|N(S)| < |S|$ for $S = X \setminus X'$.

Conclusion:
If the graph satisfies the condition of Hall's theorem, there must be a perfect matching.