# 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.

• And if the graph has only one vertex? I'm guessing your book defines graph so this can't be the case. – Fizz Jan 31 '15 at 10:11
• Oh yes, I forgot to add the assumption that it has at least 2 vertices. – Superman Jan 31 '15 at 10:13
• This is excellent. – Brian M. Scott Jan 31 '15 at 12:01
• You could've just stopped when you found the $n+1$ length path, as that contradicts the maximality of your initial path and hence both $u$ and $v$ have to be leafs. – F.Webber Oct 27 '15 at 18:45
• This is an old question, but there's still a relevant comment to make: this is true only under the additional hypothesis that the graph has finitely many vertices. An infinite tree can have zero leaves. The real line $\mathbb{R}$ with vertex set $\mathbb{Z}$ is an example. – Lee Mosher Feb 10 '18 at 22:29

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.