I need help proving this:

Given a graph $G$, prove that if in all subgraphs of $G$ there is a vertex of degree less than $2$ ($1$ or $0$) then $G$ is a forest.

  • 1
    $\begingroup$ Where do you get stuck? Plug in the definition of forest, tree, subgraph. $\endgroup$ Jun 19, 2013 at 16:38
  • 4
    $\begingroup$ Assume there is a cycle in $G$... $\endgroup$ Jun 19, 2013 at 16:39
  • $\begingroup$ Is it sufficient to prove that in all connected components of $G$ there is no cycle and that means it is a forest? $\endgroup$
    – TheNotMe
    Jun 19, 2013 at 16:45
  • $\begingroup$ What can those connected components look like? Consider subgraphs with three vertices. $\endgroup$
    – dfeuer
    Jun 19, 2013 at 16:48
  • 1
    $\begingroup$ Thank you so much for the hint, Damian Sobota. I proved it. $\endgroup$
    – TheNotMe
    Jun 19, 2013 at 16:53

1 Answer 1


Have you tried to prove the contrapositive? Like Damian said, assume that G is not a forest. Then it has a cycle. This cycle is a subgraph. What is the minimum degree of any vertex in a cycle?

To do this proof you just need to make sure you know the definitions of forest, cycle, and vertex, and that you know how to use contraposition. Wikipedia has a definition and some examples if you need help with how to use this.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .