Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Where do you get stuck? Plug in the definition of forest, tree, subgraph. –  Hagen von Eitzen Jun 19 '13 at 16:38
4  
Assume there is a cycle in $G$... –  Damian Sobota Jun 19 '13 at 16:39
    
Is it sufficient to prove that in all connected components of $G$ there is no cycle and that means it is a forest? –  TheNotMe Jun 19 '13 at 16:45
    
What can those connected components look like? Consider subgraphs with three vertices. –  dfeuer Jun 19 '13 at 16:48
1  
Thank you so much for the hint, Damian Sobota. I proved it. –  TheNotMe Jun 19 '13 at 16:53
show 1 more comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.