Proof for Full Binary Tree Using Handshaking Lemma?

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$$

• So simple, thanks. – 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.

• The book offers this proof. I was really trying to use the H.S. Lemma here but I think I may have confused myself. – wazy Oct 6 '12 at 19:30
• @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. – Brian M. Scott Oct 6 '12 at 19:33
• The stronger version is usefull for trees, because it can be combined with the tree formula. – N. S. Oct 6 '12 at 19:36