0
$\begingroup$

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.

2 Answers 2

2

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$

  • 0
    So simple, thanks.2012-10-06
2

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.

  • 0
    The stronger version is usefull for trees, because it can be combined with the tree formula.2012-10-06