그래프이론(Graph Theory) 문제풀이 하겠습니다. 풀려고 하는 문제는 “Let G be a simple graph with diameter at least 4. Prove that \bar{G} has diameter at most 2.” 입니다.
그래프이론(Grpah Theory)문제풀이
Let G be a simple graph with diameter at least 4. Prove that \bar{G} has diameter at most 2.
풀이)
G는 diameter가 4이상이므로 vertex가 5개 이상 존재한다. u,v 를 d_G(u,v)=diam(G) 가 만족되게하는 vertices라고 가정하자. edge u,v 는 G 에서 존재하지 않고 \bar{G} 에서 존재한다. 따라서 d_{\bar{G}}(u,v) = 1
여기서 임의의 vertices w_1,w_2를 주자. 여기서 w_1, w_2 \notin \{u,v\} 이다.
Case1) w_1, w_2 가 G 에서 adjacent 하지 않다면 \bar{G} 에서 adjacent 하므로 d_{\bar{G}}(w_1,w_2) =1
Case2) w_1, w_2 가 G 에서 adjacent 한 경우.
여기서 주목해야 할것이 w_1, w_2 모두 G상에서 동시에 u,v 에 adjacent 할 수 없다는 점이다. 동시에 adjacent 할 경우 diam(G) 는 2가 되므로!
Case2.1) w_1, w_2 둘 다 u,v 에 G상에서 adjacent한 점이 없을 경우 \bar{G} 상에서 path w_1 - v - w_2 가 존재한다. 따라서 d_{\bar{G}}(w_1,w_2) = 2
Case2.2) w_1,w_2 둘 중 하나가 u,v 의 vertex중 하나에 G상에서 adjacent한 경우. 예를 들어 w_1 가 G상에서 u 와 adjacent 하다고 가정하자. 그러면 w_2 는 G상에서 v 와 adjacent 하지 않다. adjacent 하다면 diam(G) 가 줄어들기 때문이다. 그러면 \bar{G} 에서 path w_1 - v - w_2 가 존재한다. 그러므로 d_{\bar{G}}(w_1, w_2) =2
위의 사항들을 종합하면 임의의 vertex w_1, w_2 에 대하여 d_{\bar{G}}(w_1, w_2) \leq 2 이다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 5 문제