Proof
(related to Lemma: Lower Bound of Leaves in a Tree)
- By hypothesis, \(T(V,E,\gamma)\) is a tree of order \(|T|\ge 2\).
- According to equivalent definitions of trees, for every pair of vertices \(u,v\in V\) there is exactly one path \(P^k:=x_0x_1\ldots x_{k-1}x_k\) in \(T\) with \(x_0=u\) and \(x_k=v\).
- Choose \(u,v\) such that \(P^k\) will have a maximal length \(k\).
- Since \(P^k\) is maximal, \(\delta_T(u)\in P^k\) with \(\delta_G(u)=\{e\in E: u\in \gamma(e)\}\).
- Therefore, the degree \(d_T(u)=|\delta_T(u)|=1\).
- Similarly for \(v\in V\).
- Therefore, \(T\) has at least the two leaves \(u\) and \(v\).
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000