Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Where do you get stuck? Plug in the definition of forest, tree, subgraph. – Hagen von Eitzen Jun 19 '13 at 16:38
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
Thank you so much for the hint, Damian Sobota. I proved it. – TheNotMe Jun 19 '13 at 16:53
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|cite|improve this answer

Your Answer


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.