[Math] Every tree has two leaves. Is the proof ok

graph theoryproof-verification

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.

Best Answer

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.

Related Question