◀ ▲ ▶Branches / Graph-theory / Proof

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

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000