Prove or disprove: Every tree T has at least $∆(T)$ leaves.

문제출처

광주과학기술원(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.