Every tree has two leaves. Is my proof ok?

A tree is a connected acyclic graph. A leaf is a vertex of degree one. The distance $d(u,v)$ between two vertices $u$ and $v$ of a graph is the length of the shortest path from $u$ to $v$.

Theorem. Every tree $G$ on at least two vertices has at least two leaves.

Proof. Let $G$ be a tree. Let $u$ and $v$ be vertices of $G$ with maximum distance, say $n$. Claim both $u$ and $v$ are leaves. Let $p_0,\ldots,p_n$ be a path of length $n$ with $p_0=u$ and $p_n=v$. Suppose $v$ is not a leaf. Then there exists a vertex $w$ adjacent to $v$ which is not $p_{n-1}$. Since $G$ is acyclic we know that in fact $w$ is not any $p_i$.

Let $p_{n+1}=w$. We know $p_0 ,...,p_n,p_{n+1}$ is a path (vertices are distinct), clearly of length $n+1$. There must be a shorter path $W$ from $p_0$ to $p_{n+1}$. There exists a $p_i$ such that $p_i\in W$ but $p_{i+1}\notin W$. Let $$m=\min\{i<j\leq n+1:p_j\in W\}.$$ Then $p_i,...,p_m$ must be part of a cycle in $G$. Contradiction.

This is very different from what my book has, but this seemed like the natural way to prove the theorem.

Solution 1:

As F.Webber indicated, it suffices to select the endpoints of a maximal path, since such a path can neither be extended nor loop back on itself.

Alternatively, you can prove this by induction. Base Case: The $2$-vertex tree has two leaves. Induction: Every tree with at least $3$ vertices can be constructed by attaching a pendent edge to a smaller graph; the additional edge adds a new leaf and covers at most one leaf.