그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “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.” 이다.
그래프이론 (Graph Theory) 문제풀이
이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.
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.
이제 이 문제를 풀어보려고한다. G 를 n(G) = n \geq 4 인 그래프라고 하자. \delta(G) = n-1 이거나 \delta(G) = n-2 이다.
\delta(G) = n-1 인 경우
이 때 graph G 는 complete graph 이므로 \kappa(G) =n-1
\delta(G) = n-2 인 경우
w \in V(G) 를 임의의 vertex라고 합시다.
u,v \in V(G) 를 w 와는 다른 서로다른 두 vertex 라고 합시다.
deg_{G}(w) \geq n-2 이므로 w 는 u 또는 v 와 adjacent 할 수 밖에 없습니다.
w 가 u 와 adjacent 라고 가정합시다.
u 가 v 와 adjacent 경우
u,v 가 adjacent 하다면 G-w 에서 uv – path 가 존재합니다.
u 가 v 와 adjacent 하지 않는 경우
\delta(G) = n-2 이므로 잘 계산해보면 N_G (u) = N_G(v) 입니다.
따라서 G-w 에서 uv -path 가 존재합니다.
위의 두 경우에서 알 수 있듯 w 를 제거해도 G- w 는 connected라는 점입니다.
이 사실을 이용해서 이제 본 문제를 풀도록 하죠.
V(G) = \{ v_1, v_2 ,...,v_n \} 라고 합시다.
그리고 deg_G(v_1)=\delta(G), N_G(v_1) =\{ v_2,...,v_{n-1} \} 라 합시다.
H_0: =G 이고 H_i := H_{i-1} - v_{i+1} , i=1,2,3,...,n-3 라 합시다.
그러면 H_i 는 connected 이고 \delta(H_i) = n-2-i 입니다.
H_{n-3} 는 3개의 vertex로 구성되어있고 \delta(H_{n-3})=1 이므로 H_{n-3} 는 path 입니다.
따라서 \kappa(H_{n-3}) = 1 이고 \kappa(G) = n-2입니다.
Best possible inequality 인 이유
H_1 = K_2 , H_2 = K_2 , H_3 = K_{n-4} 라 하고 서로 disjoint 라고 합시다.
각각의 i =1,2에 대해 H_i의 모든 vertex와 H_3 위의 모든 vertex를 이어버려서 graph G 를 만듭시다.
그러면 \kappa(G) = n-4 이고 \delta(G) = n-3 입니다.
[그래프이론 (Graph Theory) 문제풀이] Determine κ and κ′ for each graph below.
[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 6 문제