2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I should have mentioned Every non-trivial graph. My Bad. $\endgroup$
    – Babai
    Jun 30 '19 at 12:13
2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is it possible to prove without using the fact that for a tree $n=e+1$? $\endgroup$
    – Babai
    Jun 30 '19 at 14:36
  • $\begingroup$ 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. $\endgroup$
    – ArsenBerk
    Jun 30 '19 at 15:18
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If we use induction we will end up proving every vertex has degree 0 or 1, is not it? $\endgroup$
    – Babai
    Jun 30 '19 at 14:37
  • $\begingroup$ @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$. $\endgroup$ Jun 30 '19 at 14:42

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.