12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ And if the graph has only one vertex? I'm guessing your book defines graph so this can't be the case. $\endgroup$ – Fizz Jan 31 '15 at 10:11
  • $\begingroup$ Oh yes, I forgot to add the assumption that it has at least 2 vertices. $\endgroup$ – Superman Jan 31 '15 at 10:13
  • 1
    $\begingroup$ This is excellent. $\endgroup$ – Brian M. Scott Jan 31 '15 at 12:01
  • 4
    $\begingroup$ 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. $\endgroup$ – F.Webber Oct 27 '15 at 18:45
  • $\begingroup$ 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. $\endgroup$ – Lee Mosher Feb 10 '18 at 22:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ complete induction or regular induction? $\endgroup$ – user420360 Jun 8 '17 at 16:40
  • $\begingroup$ @brittany Regular: When attaching a pendent edge to a smaller graph, you only need the previous case (1 less vertex). $\endgroup$ – Danny Rorabaugh Jun 13 '17 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.