Prove that a tree in which every vertex has degree at most 2 is a simple path

Question

Prove that a tree in which every vertex has degree at most 2 is a simple path. More precisely:

Let $G = (V,E)$ be an undirected tree, with $|V| = n \geq 1$ and assume that every vertex has degree at most $2$. Then $V$ can be ordered into a simple path $\langle v_1 ..... , v_n\rangle$ and it uses all edges in $E$.

---

I'm not sure how to even start with this problem here. So a tree is a graph such that it has no cycles and this particular tree has vertex's with degree AT MOST 2. That means that the first and last vertex will have 1 edge and every vertex in between will have 2. That should be a simple path. I don't know how to prove this formally. Any help? should I be using an adjacency matrix anywhere?

thanks.

Answer 1

HINT: Prove it by induction on $n$. The case $n=1$ is trivial. Suppose that you’ve proved it for some $n\ge 1$, and consider a tree $G$ with $n+1$ vertices, all of degree at most $2$.

• $G$ has a vertex $v_0$ of degree $1$; why?
• Show that $G-v_0$ is a tree in which every vertex has degree at most $2$.
• Apply the induction hypothesis to $G-v_0$.
• Use the previous step to show that $G$ is a path with $v_0$ at one end.