그래프이론 문제를 풀려고 한다. 풀려는 문제는 “Let T be an n-vertex tree having one vertex of each degree i with 2≤i≤k; the remaining n-k+1 vertices are leaves. Determine n in terms of k.” 이다. n개의 vertex로 구성된 Tree가 있다고 하자. i=2,3,…,k 마다 i를 degree를 갖는 vertex가 한개씩 존재하고 나머지 vertex는 다 leaf라고 한다. 이 때 n을 k에 의해 결정하라는 문제이다.

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

풀려고 하는 문제를 다시 작성해보자.

Let T be an n-vertex tree having one vertex of each degree i with 2≤i≤k; the remaining n-k+1 vertices are leaves. Determine n in terms of k.

T 의 vertex의 갯수는 n 개 이므로 tree의 특성에 따라 T의 엣지의 갯수는 e(T) = n-1 이다. 그리고 이제 degree의 합을 구해보자. 문제의 가정에 의해 degree의 합은 아래와 같이 구할 수 있다.

결론을 정리하면 \sum_{v \in V(T)} deg_T (v) = \frac{k(k-1)}{2} + n 이다. degree의 합의 edge의 갯수의 2배 이므로 아래와 같이 식을 전개해보자.

따라서 n = 2 + \frac{k(k-1)}{2}