[Math] A tree with exactly two leaves is a path

graph theory

I need to prove that

if $A$ is tree with only two leaves then $A$ is a path.

I don't know if this is ok, can you help me?

Let $A$ be a tree with exactly 2 leaves.
Let $u$ and $v$ $\in V(A)$ be the leaves.
If $A$ is not a path, it means that exists $v_i\in V(A)$ which $d(v_i)\geq 3$ (degree) and a vertex $w\in V(A)$ where the edge $(v_i,w) \in E(A)$.

If $d(w)=1$ then $w$ is a leaf. That's a contradiction because $A$ only has two leaves.

If $d(w)\geq 2$ then exists a vertex $y\in V(A)$ and $d(y) = 1$ so that exists a $wy-path$, then $y$ is a leaf and that's a contradiction.

Best Answer

I think that you may have the right general idea, but so many details are missing that I can’t be sure. For instance, you’ve said nothing that would rule out the possibility that $y=u$ or $y=v$.

Try this. Since $A$ is a tree, there is a (unique) simple path $P$ from $u$ to $v$. Let the vertices of $P$ be $u=v_0,v_1,\ldots,v_n=v$ in order from $u$ to $v$. If $P$ is all of $A$, you’re done, so suppose that there is a vertex $w$ not on $P$. Then there is a simple path $Q$ from $w$ to $u$.

  • Show that there must be a vertex $v_k$ lying on both $P$ and $Q$.

Let $m$ be maximal such that $x_m$ is on both $P$ and $Q$.

  • Show that there is an edge $e=\{v_m,x\}$ incident at $v_m$ that is on $Q$ but not on $P$.

Remove the edge $e$; this breaks the tree $A$ into two components, one containing $P$ and the other containing the vertex $x$. Let $C$ be the component containing $x$. $C$ is a tree, and $x$ is a leaf of $C$. Every tree has at least two leaves, so let $y$ be another leaf of $C$.

  • Show that $y$ is a leaf of $A$, contradicting the hypothesis that $A$ has only two leaves.
Related Question