The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction.

We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole graph is a tree --> trees can't have a cycle --> contradiction --> therefore, the sub-graph does not have a cycle --> therefore, the sub-graph must also be a tree

however, another property of a tree is that it is connected. is our first proof sufficient for proving P or do we need to write another proof that talks about cycles?

I guess my real question is about how finding a contradiction can actually prove a proposition when you are only showing the contradiction in one of many possible properties (i.e. acyclic, rather than connected)

  • 4
    $\begingroup$ A subgraph of a tree is general only a forest. $\endgroup$ Apr 2, 2014 at 6:46
  • $\begingroup$ Here is a good example to add onto Hagen's comment. Consider $P_{3}$, a path on three vertices. Let $G \subset P_{3}$, with $V(G) = \{ v_{1}, v_{3} \}$, the endpoints of $P_{3}$; and $E(G) = \emptyset$. We have a forest, not a tree. $\endgroup$
    – ml0105
    Apr 2, 2014 at 13:26

1 Answer 1


If the assumption that a proposition is false leads to a contradiction, then the assumption is incorrect and the proposition must be true. In the proof that every subgraph of a tree is a tree we are given that the graph is connected since it is a tree and trees are connected by definition. Thus using the property that trees are acyclic is the best approach to take for this problem. The proof is perfect.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .