1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Not connected $\not \Rightarrow$ Has isolated vertex $\endgroup$
    – M. Vinay
    Jun 12, 2014 at 12:33
  • $\begingroup$ A disconnected subgraph of a forest is itself a forest. It does not necessarily have an isolated vertex. But a forest always has a subgraph that is a tree. So the case of a disconnected subgraph can be reduced to the first case (tree). And yes, you have to prove that every tree has a leaf, unless the context of the problem implies that you can use it as a known result. But then there is hardly anything to prove. $\endgroup$
    – M. Vinay
    Jun 12, 2014 at 12:35
  • $\begingroup$ Thanks for you comment! So basically I can say that in the case of a disconnected subgraph we can also divide it into 2 cases: connected and then it's a tree or disconnected again and we subgraph it until there are no more options. Can you help me with prooving the fact that a tree has to have a leave? thanks $\endgroup$ Jun 12, 2014 at 12:44
  • $\begingroup$ "... in the case of a disconnected subgraph we can also divide it into 2 cases: connected and ...". Read that again, it makes no sense. If the case is that of a disconnected subgraph, how can it be connected at the same time?! And you don't need to keep dividing it until you reach a connected subgraph. Just consider the connected subgraph directly. $\endgroup$
    – M. Vinay
    Jun 12, 2014 at 12:47
  • $\begingroup$ but every disconnected subgraph has a connected component, which is what i was referring to... $\endgroup$ Jun 12, 2014 at 12:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think this is a better proof, wannabe programmer. $\endgroup$
    – M. Vinay
    Jun 12, 2014 at 13:02
  • $\begingroup$ That's just beautiful. Thank you sir! $\endgroup$ Jun 12, 2014 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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