0
$\begingroup$

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.

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

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.
| cite | improve this answer | |
$\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.