Prove:

Let T be a tree with at least two vertices and let v be an element of V(T). If v is not a leaf, then T - v is not a tree.

Printable View

- Dec 11th 2009, 11:24 AMdynas7yProof Involving Trees and Leafs
Prove:

Let T be a tree with at least two vertices and let v be an element of V(T). If v is not a leaf, then T - v is not a tree. - Dec 11th 2009, 11:50 AMIsomorphism
Consider the following definition of the tree:

"Any two vertices in T can be connected by a unique simple path."

Since v is not a leaf node and T has at least two vertices, v must have at least two nodes connected to it. Call them x and z. Clearly by the definition of a tree,path between x and z is only via v.*the*

If T - v is a tree, then there still exists a unique simple path between x and z when v has been removed. This contradicts the fact that the path between x and z is only via v.