6
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ To simplify your argument, take the longest path in $T$ and consider its end points. $\endgroup$
    – hbm
    Mar 30, 2014 at 20:40
  • $\begingroup$ 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. $\endgroup$
    – ml0105
    Mar 31, 2014 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – janes
    Apr 20 at 6:39

1 Answer 1

9
$\begingroup$

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.

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

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.