Problem
COM-B1-M09-P016 Two Leaves
#16
★★★☆☆ Level 3 of 5
Prove that every tree with at least two vertices has at least two vertices of degree \(1\).
Take a longest simple path.
Consider a longest simple path in the tree. Let one endpoint be \(v\). If \(v\) had a neighbor outside the path, the path could be extended, contradiction. If \(v\) had a neighbor on the path other than the nearest one, a cycle would appear, impossible in a tree. Thus \(v\) has exactly one neighbor, degree \(1\). The same holds for the other endpoint.
Classic longest-path technique.