Prove that every subgraph of forest has at least one vertex of degree < 2

917 Views Asked by At

So I know that a forest is a graph that has no cycles. This is what I had in mind:

Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a tree and a tree has to have a leaf (should i prove that? i'm not sure how) if it's not connected, then at least one vertex isn't connected to any other vertex which means it's of degree 0.

That's the basic idea... I need some elaboration.

1

There are 1 best solutions below

2
On BEST ANSWER

Proof by contradiction:

Suppose every vertex of T has degree at least 2. Start with a vertex $v_1$ in T. Follow one of the edges from $v_1$ to reach another vertex $v_2$. Each time you reach $v_i$ from $v_{i-1}$, choose $v_{i+1}$ as one of the neighbors of $v_i$ other than $v_{i-1}$. (can always do this since $v_i$ has degree >= 2). In this way we get a sequence $v_1, v_2, v_3, ... v_k, ...$. Since T has finitely many vertices, say n, there must be a repeated value in $v_1, v_2, v_3, ... v_{n+1}$. Suppose $v_i = v_j$, with i < j. Then $v_i, v_{i+1}, ... v_j$ forms a cycle, which should not happen as T is a subgraph of a forest.