0
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.