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)
Best Answer
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.