I was told a tree has non-leaf vertices with degrees $5,5,5,8,10$, and I was told to calculate how many total vertices there are.

I thought to draw the tree in three levels - top one is a choice of a root, middle one is other non-leaf vertices and remaining leaves, and lowest one is the remaining leaves.

Then we assign "corrected degrees" telling us how many vertices are below each vertex. This leaves the root fixed and lowers all other degrees by $1$. So if we start with non-leaf vertices $v_1,\dots ,v_n$, the result should be $(\sum_{i=1}^n\deg v_i)-(n-1)$. Is this correct?


HINT: Suppose that there are $n$ leaves. Then the sum of the degrees of the vertices is $33+n$, and there are $n+5$ vertices altogether. Use the handshaking lemma and the fact that a tree has one more vertex than it has edges to solve for $n$.

  • $\begingroup$ I haven't learned the handshaking lemma yet. Is my attempt wrong? $\endgroup$ – combinarcotics Sep 15 '16 at 23:04
  • $\begingroup$ @combinarcotics: I’m afraid so, because there’s no guarantee that all of the other interior vertices are adjacent to the root: you might need more levels. The handshaking lemma is easy: it just says that the sum of the degrees of the vertices in any graph is twice the number of edges. This is because each edge has two ends, so when you add the degrees of the vertices, you’re counting each edge twice. $\endgroup$ – Brian M. Scott Sep 15 '16 at 23:05
  • $\begingroup$ That problem occurred to me but I got confused since it seemed I can draw tree with given non-leaf degrees to have just three levels - pick a root, connect all interior vertices to it, and connect to everything however many leaves are needed. What am I missing here? $\endgroup$ – combinarcotics Sep 15 '16 at 23:12
  • $\begingroup$ @combinarcotics: You’re missing the fact that that isn’t the only possibility. You need to make sure that you give an argument that covers every possible tree with the specified degrees. $\endgroup$ – Brian M. Scott Sep 15 '16 at 23:13
  • $\begingroup$ By that do you mean some trees can be drawn with different numbers of levels, or that not all trees may be drawn this way? I'm guessing it's the latter? $\endgroup$ – combinarcotics Sep 15 '16 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.