Let T be a tree with n >= 2 vertices and let v e V(T). Prove that if T - v is a tree, then v is a leaf.

How does one go about solving this?

Printable View

- May 6th 2008, 04:09 PMjzelltTrees
Let T be a tree with n >= 2 vertices and let v e V(T). Prove that if T - v is a tree, then v is a leaf.

How does one go about solving this? - May 6th 2008, 08:24 PMangel.white
My suggestion would be to find a theorem in your book that says something along the lines of "a tree is defined as a connected graph where there is a unique simple path between any two vertices" then point out that if the graph is unique, then there are no circuits, so breaking that path (removing any vertice along the path) would cause the tree to become unconnected. Thus it is not a tree. So if you remove a node, and the tree is still a tree, then that node cannot be along the path between any two nodes, thus it must have only one edge associated with it, and therefore must be a leaf.

You'll want to find the theorems that define a tree as I have defined it, and that define a leaf as a node with only one edge, and then reword it to be more rigorous.