# 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.