# A tree has at least two leaves (proof by contradiction)

I would like you to tell me if the proof is correct and how can I improve the formalisation of it. Also, if all the assumptions/steps of the proof are correct.

A tree has at least two leaves. (proof by contradiction.)

I intend to prove the above statement, and to do so I proceed by contradiction.

Let $$T$$ be a tree of order $$n \geqslant 2$$, in which we assume the number of leaves is $$< 2$$.

It must have at least one leaf, otherwise we would have a cycle. Then, let us call that leaf $$l$$.

Consider the path that starts at $$l$$, and follows to any other vertex $$v$$. If $$v$$ is a leaf, we are done. Otherwise it must be adjacent to at least another vertex $$u$$. Repeat the reasoning for $$u$$.

Thereby, our path can only end in a leaf (which is not possible by assumption) or in an already visited vertex creating a cycle (which is not possible by assumption since the graph we consider is a tree) and hence we found a contradiction.

P.S: sorry for the wrong math symbols,

A lot of thanks to all of you!

• To simplify your argument, take the longest path in $T$ and consider its end points.
– hbm
Mar 30, 2014 at 20:40
• A small point as well- it's probably worth noting that $T$ has finite order. If $T$ is an infinite graph, your proof doesn't hold. Mar 31, 2014 at 13:43
• Take a path of maximal length. The start/end nodes must have degree 1 otherwise we can a) extend the path or b) create a cycle in the path. Apr 20 at 6:39

I'm convinced. Your proof looks good to me.

Another way to do this would be with a handshake argument. I think this argument is perhaps a bit easier to see. An equivalent definition of a tree with $n$ vertices is that it has $n-1$ edges. So let's assume exactly one leaf. Then every other vertex has degree at least $2$. So by the Handshake Lemma, $\sum_{v \in V(T)} d(v) = 2n - 2$. Since every vertex except the one leaf has degree at least $2$, we get $2 \sum_{v \in V(T)} d(v) \geq 2[2(n-1) + 1] = 4n - 2 > 2(n-1)$, a contradiction.

• Alright, so you add up all degrees on one side and on the other side you summ all edges, quick and clean, thanks! Mar 30, 2014 at 17:38