Prove or disprove: (a) every graph with connectivity 4 is 2-connected. (b) every k-connected graph is k-edge-connected.

문제출처

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

---

Solution

(a) Every graph with connectivity 4 is 2-connected.

• For Connectivity 4 graph, we need to delete at least 4 vertex to disconnect the graph. And for 2-connected graph, If we delete one vertex it still remain connected. By the definition of connectivity and $k$-connected, It is true.

(b) Every k-connected graph is k-edge-connected.

• For a $k$-connected graph, there exist at least $k$ vertex-disjoint paths.

• For a $k$-edge-connected graph, there exist at least $k$ edge-disjoint paths.

• By Menger's theorem, for any pair of vertices $u, v \in G$:
  $$\lambda_G(u, v) = \kappa_G(u, v),$$
  where:

  • $\lambda_G(u, v)$ is the maximum number of edge-disjoint paths between $u$ and $v$, and
  • $\kappa_G(u, v)$ is the maximum number of vertex-disjoint paths between $u$ and $v$.

• Therefore, by Menger's theorem, every $k$-connected graph is also $k$-edge-connected.