Problem
COM-B2-M04-P004 A Leaf in a Tree
#4
★★☆☆☆ Level 2 of 5
Prove that every finite tree with at least two vertices has a vertex of degree \(1\).
Take a longest simple path in the tree.
Choose a longest path \(v_1v_2\ldots v_k\) in the tree. If \(v_k\) has a neighbour outside the path, the path can be extended, impossible.
If \(v_k\) is adjacent to an earlier vertex of the path other than \(v_{k-1}\), a cycle appears. A tree has no cycles. Thus the only neighbour of \(v_k\) is \(v_{k-1}\), so the degree of \(v_k\) is \(1\).
This problem shows how an extremal path gives a structural property of a tree.