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

1.2k Views Asked by At

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.

2

There are 2 best solutions below

2
On

The claim is not true. The graph with a single vertex and no edges is acyclic but does not have two vertices of any description.

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.

2
On

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?