Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.

문제출처

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

---

Solution

1. Since $G$ is a 3-regular graph, $\delta(G) = 3$. Thus, $\kappa(G) \leq \kappa'(G) \leq \delta(G) = 3$.

2. Consider $\kappa(G) = 0$:

• If $G$ is disconnected, $\kappa'(G) = 0$.
• Thus, $\kappa(G) = \kappa'(G) = 0$.

3. Consider $\kappa(G) = 1$:

• Let the vertex cut $S = {v_1}$.
• There are two components $C_1$ and $C_2$ in $G \setminus S$.
• Since $G$ is a 3-regular graph, one of the two components must have only one edge incident with $v_1$.
• Thus, $\kappa'(G) = 1$, and $\kappa(G) = \kappa'(G) = 1$.
• Example:

4. Consider $\kappa(G) = 2$:

• By Menger's theorem, $\kappa(x, y) = \lambda(x, y)$ for any $x, y \in V(G)$.
• Under the condition $\kappa(G) = 2$, the maximum number of edge-disjoint paths between $x$ and $y$ is 2.
• Thus, $\kappa(x, y) = \lambda(x, y) = 2$.
• Since $\kappa'(G)$ can be represented as $\min_{x, y \in V(G)} \lambda(x, y)$, we have $\kappa(G) = \kappa'(G) = 2$.

5. Consider $\kappa(G) = 3$:

• Since $3 = \kappa(G) \leq \kappa'(G) \leq \delta(G) = 3$, we have $\kappa(G) = \kappa'(G) = 3$.

6. Therefore, for every 3-regular graph $G$, $\kappa(G) = \kappa'(G)$ holds.