Thread: Rooted Trees

Hi.

I'm having trouble with this 'show' this question.

Show that any rooted tree with at least two vertices contains a non-terminal
vertex such that all of its children are terminal vertices.

I can see why this is the case visually. Quite logical in fact. How do I show that the children of the two vertices are actually terminal vertices. Drawing it out is a piece of cake, but showing it in words... its a different story!!

Any help would be great!

You can try using contradiction.

For example, take an arbitrary rooted tree with at least two vertices. You need to show that there exists at least 1 non-terminal vertex with said property. So for contradiction, you can assume that there is NO such vertex, i.e. there isn't any non-terminal vertex, all of whose children are terminal. An equivalent statement is: for each non-terminal vertex, one or more children are non-terminal. From this, I think, you can get a contradiction very easily.

Must be a finite tree, otherwise it's false.

Take a terminal node t with maximal distance to the root. The maximal distance must be finite, because the tree is finite. Since there are at least 2 nodes, t can't be the root itself, so it has a parent p. p has the property you're looking for.