문제출처
광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4
Solution
1. Let $v$ be a vertex in $T$ with degree $\Delta(T)$, where $d(v) = \Delta(T)$. That is, $d(v)$ is the degree of vertex $v$.
2. $v$ has adjacent vertices $w_1, w_2, \dots, w_{d(v)}$. That is, there exist edges $vw_i$ incident to $v$ for $1 \leq i \leq d(v)$.
3. Now, for every edge $vw_i$ incident to $v$, take a longest path starting with $vw_i$.
4. Since there is no cycle in a tree, the last vertex of each longest path starting with $vw_i$ is a leaf.
5. Since the degree of vertex $v$ is $\Delta(T)$, we have $\Delta(T)$ paths starting at $v$.
6. At this point, every path starting with $vw_i$ is disjoint \(except at $v$\) and each ends in a different leaf.
- This is because a tree does not contain cycles.
7. Conclusion: Since there are $d(v) = \Delta(T)$ edges incident to $v$, there are at least $\Delta(T)$ leaves in the tree.