Science Advisor
- 1,229
- 0
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.
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.