1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

5-ary trees

  1. Oct 24, 2006 #1

    0rthodontist

    User Avatar
    Science Advisor

    This was a question on the combinatorics midterm: if a tree contains only vertices of degree 5 and degree 1, and the tree has 4n+2 vertices, how many vertices of degree 5 are there?

    With k the # of vertices of degree 5 and j the # of vertices of degree 1, the accepted answer used the formulas 5k + j = 8n + 2 (in other words sum over degrees of vertices = 2e) and k + j = 4n + 2 to reach the conclusion k = n.

    I used the (fact)? that a 5-ary tree with k internal vertices has 5k + 1 total vertices, to get k = (4n+1)/5. This was marked wrong. I believe that the contradiction between the two answers shows that there is no 5-ary tree with 4n+2 vertices for any n. Is my reasoning incorrect? Is there a 5-ary tree with 4n+2 vertices? Maybe I am confused.
     
  2. jcsd
  3. Oct 24, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    Ah, I got it. A tree with all vertices of degree 5 or 1 is not usually a 5-ary tree.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 5-ary trees
  1. Tree Traversals (Replies: 4)

  2. Semantic tree? (Replies: 2)

Loading...