# Proving that a sub-graph of a tree is a tree

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)

• A subgraph of a tree is general only a forest. Apr 2, 2014 at 6:46
• 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. Apr 2, 2014 at 13:26