Results 1 to 3 of 3

Math Help - Rooted Trees

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2010
    Posts
    44
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. rooted tree
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2010, 03:21 PM
  2. rooted ternary tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 8th 2010, 02:23 PM
  3. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 11:43 AM
  4. Components of Algebra rooted in pre-cal?
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: June 3rd 2008, 04:20 PM
  5. Cube rooted integral
    Posted in the Calculus Forum
    Replies: 5
    Last Post: December 15th 2007, 06:50 AM

Search Tags


/mathhelpforum @mathhelpforum