# Show that every acyclic graph has at least two vertices with degree less than 2

Show that every non-trivial acyclic graph has at least two vertices with degree less than 2.

Attempt: We know that if every vertex of $$G$$ has a degree at least 2 then $$G$$ contains a cycle. Now, since $$G$$ is acyclic $$G$$ has at least one vertex (say, v_1) with degree 0 or 1. I am not sure how to proceed further.

Can I delete the vertex $$v_1$$ from $$G$$ and claim that $$G-\{v_1\}$$ is also acyclic and use some recursive argument.

• I should have mentioned Every non-trivial graph. My Bad. Jun 30 '19 at 12:13

By definition, if $$G$$ is acyclic, then $$G$$ is a forest. WLOG, suppose $$G$$ is connected. Then $$G$$ is a tree and therefore, we have $$n = e+1$$. We also know that by Handshaking Lemma, we have $$2e = \sum_{i =1}^nd(v_i)$$ Which implies that $$2(n-1) = \sum_{i =1}^nd(v_i) \implies 2n-2 = \sum_{i =1}^nd(v_i)$$ Can you conclude your result from here?
• Is it possible to prove without using the fact that for a tree $n=e+1$? Jun 30 '19 at 14:36
• For this argument, I don't think so. But maybe you can say something like "any connected acyclic graph with $n$ vertices can be constructed by adding a vertex $v$ and edge incident to $v$ to some graph with $n-1$ vertices". Then you can use induction. Jun 30 '19 at 15:18
However, if you add an assumption that the graph has at least two vertices, then your strategy looks sound. A vertex of degree $$0$$ or $$1$$ is cannot be part of a cycle, so deleting that vertex cannot make the graph acyclic if it was not already acyclic. You should be able to phrase it as an induction on the number of vertices in the graph.
• @Babai: Hopefully not, since that is not true. Note that a vertex with degree 1 in $G\setminus \{v_1\}$ may have its degree increased by 1 when you reattach $v_1$. Jun 30 '19 at 14:42