Prove that a graph $G$ is a forest if and only if every induced subgraph of $G$ contain a vertex of degree at most $1$
=>
Let $G$ be a forest. Then $g$ is the collection of a bunch of trees. For the tree there at least one vertex of degree $0$ or $1$, so every induced subgraph of $G$ contain a vertex of degree at most $1$
<=
Assume that every induced subgraph of $G$ contain a vertex of degree at most $1$. I want to show that these subgraph are tree, meaning I want to show that non of them contain any cycle and all of them are connected graph. But I'm not sure how.
Best Answer
Try proving the contrapositive of the $\impliedby$ direction instead:
Indeed, since $G$ is not a forest, it contains a cycle. Now let $H$ be the subgraph of $G$ induced by the vertices of this cycle. Then since $H$ contains a cycle, each of its vertices has degree at least $2$, as desired.