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.