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

Question

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!

Answer 1

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.

Answer 2

Firstly, a nitpick: the original statement is false since a single vertex is a tree with only one leaf (or no leaves if you don't count vertices of degree zero as leaves). You should really modify the statement so you're attempting to prove something that's actually true (either explicitly making an exception for the order 1 tree only having one leaf (or zero leaves), or limiting your statement to n>1).

The claim that you require at least one leaf or else there would be a cycle is not clearly proven at a stage where you haven't yet proven that every tree has leaves. Also, it's not necessary for the rest of your proof.

Rather than starting the path at a leaf, you can start at any arbitrary vertex - if it's not a leaf, you can extend in both directions until you hit a leaf (since you can't close a cycle nor add infinitely many vertices).

You should explicitly invoke the fact that the graph is finite, otherwise you can add infinitely many vertices to your path without ever reaching a leaf.