= Solution
A <tree> is a nonempty <connected graph> with no <graph cycle>. A <leaf of a tree> is a <vertex> of <vertex degree> one. As usual in this finite <graph theory> problem, <trees> are finite; the assertion would fail for a doubly infinite <graph path>.
Take a <longest path> $v_0,v_1,\ldots,v_m$ in a <tree> with at least two <vertices>. Connectedness gives $m\ge1$. If $v_0$ had a neighbour outside this <graph path>, the path could be extended, contradicting maximal length. If it had a neighbour $v_j$ with $j\ge2$, that <edge> together with the segment $v_0,v_1,\ldots,v_j$ would make a <graph cycle>. Thus its only neighbour is $v_1$, and it is a <leaf of a tree>. The same argument at the other end makes $v_m$ a second, distinct <leaf of a tree>. Hence
$$
\boxed{\text{Every finite tree with at least two vertices has at least two leaves.}}
$$
Back to article page
