I asked a question a few days ago and figured out the proof for this theorem using induction.

If T is a full binary tree with i internal vertices, then T has i + 1 
terminal vertices and 2i + 1 total vertices.

Now as a challenge I am trying to use the Handshaking Lemma to show the same thing.

H.S. Lemma: Every finite undirected graph has an even number of vertices 
            with odd degree.

I have this written out but am stuck on how to continue.

Each vertex of a FBT has 0 or 2 children, if the child is a terminal vertex it has a degree of 1 (to its parent) and if the child is a internal vertex it has a degree of 3 (to its parent and two children). The only non-child is the root node. Because all internal vertices must have 2 children there exists 2i children. A child whether internal or terminal has a odd degree (1 or 3). Thus there are an even number of vertices 2i with odd degree.


I think this follows immediately from the stronger version of HSL:

$$\sum \mbox{degree}=2 E \,.$$

In a tree $E=V-1$, thus

$$\sum \mbox{degree}=2 V-2 \,.$$

If there are $i$ internal vertices, you have $V-i$ leaves, and thus (you already argued that the internal vertices have degree 3, excepting one of degree 2) you get

$$2+3(i-1)+ (V-i)= 2V-2 \Rightarrow V=2i+1$$

  • $\begingroup$ So simple, thanks. $\endgroup$ – wazy Oct 6 '12 at 20:11

You’re essentially done. You’ve shown that if the tree has $i$ internal vertices, it has $2i$ children. The root is the only non-child, so it has $2i+1$ vertices. Finally, $i$ of the vertices are internal, so the other $(2i+1)-i=i+1$ must be terminal. This doesn’t actually use the handshaking lemma, however: the fact that the children are the vertices of odd degree is irrelevant to the argument.

  • $\begingroup$ The book offers this proof. I was really trying to use the H.S. Lemma here but I think I may have confused myself. $\endgroup$ – wazy Oct 6 '12 at 19:30
  • $\begingroup$ @wazy: Since the lemma is a general fact about all graphs, it’s unlikely to contribute much to a proof of a result that’s very specific to trees. $\endgroup$ – Brian M. Scott Oct 6 '12 at 19:33
  • $\begingroup$ The stronger version is usefull for trees, because it can be combined with the tree formula. $\endgroup$ – N. S. Oct 6 '12 at 19:36

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.