2
$\begingroup$

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)

$\endgroup$
2
  • 4
    $\begingroup$ A subgraph of a tree is general only a forest. $\endgroup$ – Hagen von Eitzen Apr 2 '14 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 '14 at 13:26
1
$\begingroup$

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.

$\endgroup$

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.