Prove that $κ(G) = δ(G)$ if G is simple and $δ(G) ≥ n(G)−2$. Prove that this is best possible for each n ≥ 4 by constructing a simple n-vertex graph with minimum degree n − 3 and connectivity less than n − 3.

문제출처

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

아래를 참고해서 작성한 풀이인데, 풀이가 조금 찝찝하다. 조교는 한두장 분량의 원래 매우 긴 풀이를 기대했다고 한다. 다른 괜찮은 풀이를 생각해보는게 좋겠다.
https://seongqjini.com/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-graph-theory-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-prove-that-%CE%BAg-%CE%B4g-if-g-is-simple-and-%CE%B4g-%E2%89%A5-ng-%E2%88%92-2-prove-that/

---

Solution

1. Since $\delta(G) \geq n(G) - 2$, we have two cases:

• $\delta(G) = n(G) - 1$, or
• $\delta(G) = n(G) - 2$.

2. If $\delta(G) = n - 1$:

• $G$ is a complete graph.
• Then $\kappa(G) = n - 1$, and $\kappa(G) = \delta(G)$.

3. If $\delta(G) = n - 2$:

3.1. Let $u, v, w \in V(G)$ and $\deg_G(w) \geq n - 2$.

• From the assumption, $w$ must be adjacent to either $u$ or $v$.

3.2. Suppose $w$ is adjacent to $u$:

• If $u$ is adjacent to $v$, then there exists a $uv$-path in $G - w$.
• If $u$ is not adjacent to $v$, since $\delta(G) = n - 2$, $u$ and $v$ have the same neighbors.
  Thus, there exists a $uv$-path in $G - w$.
• Since $G - w$ is connected, $\kappa(G) \geq n - 2$.

3.3. Let $V(G) = {v_1, v_2, \dots, v_n}$, $\deg_G(v_1) = \delta(G)$, and $N_G(v_1) = {v_2, \dots, v_{n-1}}$.

• Construct $G_i$ by deleting one vertex at a time:
  • $G_0 = G$.
  • $G_1 = G_0 - v_2$.
  • $G_2 = G_1 - v_3$.
  • Continue deleting vertices until $G_{n-3}$.
• $G_{n-3}$ has only 3 vertices and $\delta(G_{n-3}) = n - 2 - (n - 3) = 1$.
• Thus, $G_{n-3}$ is a path graph, and $\kappa(G_{n-3}) = 1$.
• Therefore, $\kappa(G) = \delta(G)$.

4. To prove this is the best possible for each $n \geq 4$, construct a simple $n$-vertex graph with $\delta(G) = n - 3$ and $\kappa(G) < n - 3$:

4.1. Let graphs $G_1 = K_2$, $G_2 = K_2$, and $G_3 = K_{n-4}$, all disjoint.

• Construct the graph $G$ by adding edges between every vertex in $G_1$, $G_2$, and $G_3$.
• Then $\kappa(G) = n - 4$ and $\delta(G) = n - 3$.