[그래프이론 (Graph Theory) 문제풀이] Let G be a triangle-free simple n-vertex graph such that every pair of non-adjacent vertices has exactly two common neighbors. Prove that n(G) = 1 + [latex] \binom{d(x)+1}{2} [/latex] where x ∈ V (G). Hence, conclude that G is regular.

by

그래프이론 (Graph Theory) 문제풀이 글 입니다. 이번에 풀고자 하는 문제는 아래와 같습니다. Let G be a triangle-free simple n-vertex graph such that every pair of non-adjacent vertices has exactly two common neighbors. Prove that n(G) = 1 + \binom{d(x)+1}{2} where x ∈ V (G). Hence, conclude that G is regular.

이 문제는 어떻게 풀 수 있을까요?




그래프이론 (Graph Theory) 문제 풀이

다시 문제를 remind하면 아래와 같습니다.

Let G be a triangle-free simple n-vertex graph such that every pair of non-adjacent
vertices has exactly two common neighbors. Prove that n(G) = 1 + \binom{d(x)+1}{2} where x ∈ V (G). Hence, conclude that G is regular.

임의의 x \in V(G) 를 고릅니다. 그리고 d(x) 개의 neighbors v_1,v_2,...,v_{d(x)} 를 나열합니다. 이 때 삼각형이 없으므로 v_i 사이에는 edge가 없습니다. x, v_1,v_2,...,v_{d(x)} 는 총 d(x) + 1 개 인데요. 이 vertex들을 제외하면 n-d(x)-1 개의 vertex가 남습니다. n-d(x) -1 의 vertex 중 하나 w 를 선택합니다. 이 w 는 x 의 neighbor가 아닙니다. 그러므로 w ,x 는 두개의 공통된 vertex를 갖습니다. x 의 negihbors는 v_1,v_2,...,v_n 개 뿐이므로 w 는 서로다른 두 v_i , v_j 와 adjacent 하게 됩니다. 그리고 서로다른 v_i, v_j 는 nonadjacent하므로 또다른 vertex u 가 존재하여 v_i, v_j 는 u 와 x 에 adjacent 하게 됩니다. 이런식으로 앞에서 언급한 n-d(x)-1 개의 vertex 는 두개의 v_i 들에 의해 결정됩니다. 따라서 아래의 식이 성립합니다.

n-d(x)-1 = \binom{d(x)}{2}

이것을 정리하면 아래와 같은 식이 나옵니다.

n= \binom{d(x)+1}{2}+1

참고할만한 글:

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 3 문제

Leave a Comment