Hand shaking lemma and some Impotant Tree Properties.

June 23, 2019

HandShaking Lemma is one of the very nice properties of graph  and since trees form the subset of graph we can relate the theorem to trees also.

According to theorem-” Sum of Degrees of all the vertices in the graph is even .”

OR

“It can also be extended as Sum of degrees of all the vertices in graph is twice the total number of edges.”

The Following are the properties that can be derived on the basis of HandShaking lemma

1.It’s useful in finding no. of internal nodes in tree.

L= (K-1)*I+1;

the proof is left as an exercise for readers.

2. The number of leaf nodes in Binary Tree is 1  more  than nodes with two children.

Other Properties of Tree

1. The maximum number of nodes can easily be found using the formula which is 2^l -1 where l is the level number.

2. Maximum Number of Nodes in Binary tree with height h is 2^h -1.

 

2 comments on “Hand shaking lemma and some Impotant Tree Properties.”