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

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.

• This is pretty much the definition of a simple path. – Asvin Jun 21 '15 at 23:09
• @Micah: You can get angle brackets with \langle and \rangle. – Brian M. Scott Jun 21 '15 at 23:13
• @HDE 226868: See Brian's comment above. – Micah Jun 21 '15 at 23:15
• @Micah Ah, I missed that. I knew the shortcut, but forgot to insert it. – HDE 226868 Jun 21 '15 at 23:15

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.