Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook