Past exam of the short options course of the University of Oxford / 2015 / 7 / a / i / 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,\dots ,v_m$ in a tree with at least two vertices. Connectedness gives $m\ge 1$. 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\ge 2$, that edge together with the segment $v_0,v_1,\dots ,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