문제출처
광주과학기술원 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 $.