Handshaking Lemma and Trees

By | February 8, 2016

Handshaking Lemma and Trees

What is Handshaking Lemma?
Degree of a vertex is number of edges incident on it.
Handshaking Lemma states that, in every finite undirected graph, number of vertices with odd degree is always even.

The handshaking lemma is a consequence of the degree sum formula:

The vertices of odd degree in a graph are sometimes called odd nodes or odd vertices.
In this terminology, the handshaking lemma can be restated as: every graph has an even number of odd nodes.

Following are some interesting facts that can be proved using Handshaking lemma.

Property #1

In an n-ary tree where every node has either 0 or n children, following property is always true:
L = (n-1)*I + 1
Where,
L = Number of leaf nodes
I = Number of internal nodes

Proof
Case 1: Root is Leaf

There is only one node in tree.
The above formula is true for single node as L = 1, I = 0.

Case 2 : Root is Internal Node
For trees with more than 1 node, root is always internal node. A tree is an undirected acyclic graph
Total number of edges in tree is total number of nodes minus : |E| = L + I – 1.
All internal nodes except root in the given type of tree have degree n + 1. Root has degree n. All leaves have degree 1. Applying the Handshaking, we get:
Sum of all degrees = 2*Sum of edges
Sum of degrees of (leaves + root + internal node) = 2*(No. of nodes – 1)

We have:
L + (I-1)(n+1) + n = 2( L + I – 1)
Solving:
L + nI – n + I – 1 + n = 2L + 2I -2
L + nI – I – 1 = 2L + 2I – 2
nI + 1 – I = L

Therefore,
L = (n-1)*I + 1

Property #2

In Binary tree, number of leaf nodes is always one more than nodes with two children.
L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children

Proof
Case 1: There is only one node
The equation holds as T = 0, L = 1.

Case 2: Root has two children
Sum of degrees of (nodes with two children except root + nodes with one child + leaves + root) = 2*(No. of nodes – 1)
We get,
3(T-1) + 2S + L + 2 = 2(S + T + L – 1)
3(T-1) + L + 2 = 2(T + L – 1)
T – 1 = L – 2
L = T + 1

Case 3: Root has one child
Sum of degrees of (nodes with two children + nodes with one child except root + leaves + root) = 2*(No. of nodes – 1)
3T + 2(S-1) + L + 1 = 2(S + T + L – 1)
3T + 2 + L + 1 = 2(T + L – 1)
T = L – 1

Therefore, in all three cases, we get T = L-1.