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.
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Where do you get stuck? Plug in the definition of forest, tree, subgraph. $\endgroup$– Hagen von EitzenCommented Jun 19, 2013 at 16:38
-
4$\begingroup$ Assume there is a cycle in $G$... $\endgroup$– Damian SobotaCommented 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$– TheNotMeCommented Jun 19, 2013 at 16:45
-
$\begingroup$ What can those connected components look like? Consider subgraphs with three vertices. $\endgroup$– dfeuerCommented Jun 19, 2013 at 16:48
-
1$\begingroup$ Thank you so much for the hint, Damian Sobota. I proved it. $\endgroup$– TheNotMeCommented Jun 19, 2013 at 16:53
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
