Thread: Proof 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.

Originally Posted by dynas7y

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.

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, the path between x and z is only via v.
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.