# Prove every tree with at least 1 edge has 2 leaves

Prove that every tree with at least $1$ edge has at least $2$ leaves (recall that a leaf is a vertex of degree $1$).

Can anyone show me how to prove this question? Here's what I tried. Since it doesn't mention full trees, an ordered tree doesn't have to be at least $2$ leaves, some trees do have only $1$ leaf.

• Hint: Since it has at least one edge, it has a maximal path. What can you say about the end points of this path? – stochasticboy321 Jun 1 '17 at 22:10
• Of course we need to assume the tree is finite. – Cheerful Parsnip Jun 1 '17 at 22:59

Let $P$ denote the maximal in the tree (this holds for graphs as well). It exists since the graph has at least one edge. If one of the endpoints of $P$ isn't a leaf, then we can find a longer path by visiting its children....but then contradicting our assumption that $P$ is maximal.
If a tree has exactly one leaf, $v$, consider the (unique) edge $(u, v)$ incident on $v$. By hypothesis, $u$ cannot be a leaf, hence must have degree $\geq 2$. Consider an edge $(u_{1}, u)$ incident on $u$ and distinct from $(u, v)$. By hypothesis, $u_{1}$ cannot be a leaf, hence must have an edge $(u_{2}, u_{1})$ incident upon it and distinct from $(u_{1}, u)$. And so on. Thus, we would get an infinite path $v, u, u_{1}, u_{2}, \ldots$, which is impossible. This contradiction implies that there will be some $u_{k}$ that is a leaf.
If a tree has no leaves, then every vertex has degree $\geq 2$. Since the tree is connected, one can construct a cycle, contradicting the hypothesis that the graph is a tree.