Use Menger’s Theorem ($\kappa$(x, y) = $\lambda$(x, y) when $xy$ $\notin$ $E(G)$) to prove that $\alpha'(G) = \beta(G)$ when $G$ is bipartite.

문제출처

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

---

Solution

1. Suppose $G$ is a bipartite graph. We can divide $G$ into two independent and disjoint vertex sets $X$ and $Y$.

2. For $x \in X$ and $y \in Y$, add an edge ${x, y}$ to $G$ and let this new graph be $G'$.

3. In $G'$, consider:

• $\lambda_{G'}(x, y)$: the maximum number of internally disjoint $x, y$-paths, and
• $\kappa_{G'}(x, y)$: the size of the minimum $x, y$-separating set.

4. To break every $x, y$-path in $G'$, the separating set $S$ must include vertices that cover the edges of $G$. Thus, $S$ corresponds to a vertex cover in $G$. Therefore, $\beta(G) \leq \kappa_{G'}(x, y)$.

5. A set of $k$ internally disjoint $x, y$-paths in $G'$ corresponds to a set of $k$ edges in $G$ with no shared endpoints. Thus, $\lambda_{G'}(x, y) \leq \alpha'(G)$.

6. By Menger's theorem:
$$\beta(G) \leq \kappa_{G'}(x, y) = \lambda_{G'}(x, y) \leq \alpha'(G).$$

7. Therefore, both $\alpha'(G) \leq \beta(G)$ and $\beta(G) \leq \alpha'(G)$ hold.

8. Consequently, $\alpha'(G) = \beta(G)$.