3
$\begingroup$

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.

$\endgroup$
6
  • 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

5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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