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, 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

Reset to default
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$

You must log in to answer this question.

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