{"id":26983,"date":"2017-12-28T21:51:06","date_gmt":"2017-12-28T16:21:06","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26983"},"modified":"2017-12-28T21:51:06","modified_gmt":"2017-12-28T16:21:06","slug":"handshaking-lemma-interesting-tree-properties","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/handshaking-lemma-interesting-tree-properties\/","title":{"rendered":"Handshaking Lemma and Interesting Tree Properties"},"content":{"rendered":"

What is Handshaking Lemma?<\/strong>
\nHandshaking lemma is about undirected graph. In every finite undirected graph number of vertices with odd degree is always even. <\/span>The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma)<\/p>\n

    \"handshaking\"<\/pre>\n[ad type=”banner”]\n
How is Handshaking Lemma useful in Tree Data structure?<\/strong>
\nFollowing are some interesting facts that can be proved using Handshaking lemma.<\/p>\n
1) In a k-ary tree where every node has either 0 or k children, following property is always true.<\/strong><\/em><\/p>\n
  L = (k - 1)*I + 1\r\nWhere L = Number of leaf nodes\r\n      I = Number of internal nodes<\/pre>\n
Proof:<\/strong>
\nProof can be divided in two cases.<\/p>\n
Case 1<\/em> <\/strong>(Root is Leaf):There is only one node in tree. The above formula is true for single node as L = 1, I = 0.<\/p>\n
Case 2 <\/em><\/strong>(Root is Internal Node): For trees with more than 1 nodes, root is always internal node. The above formula can be proved using Handshaking Lemma for this case. A tree is an undirected acyclic graph.<\/p>\n
Total number of edges in Tree is number of nodes minus 1, i.e., |E| = L + I \u2013 1.<\/p>\n
All internal nodes except root in the given type of tree have degree k + 1. Root has degree k. All leaves have degree 1. Applying the Handshaking lemma to such trees, we get following relation.<\/p>\n
  Sum of all degrees  = 2 * (Sum of Edges)\r\n\r\n  Sum of degrees of leaves + \r\n  Sum of degrees for Internal Node except root + \r\n  Root's degree = 2 * (No. of nodes - 1)\r\n\r\n  Putting values of above terms,   \r\n  L + (I-1)*(k+1) + k = 2 * (L + I - 1) \r\n  L + k*I - k + I -1 + k = 2*L  + 2I - 2\r\n  L + K*I + I - 1 = 2*L + 2*I - 2\r\n  K*I + 1 - I = L\r\n  (K-1)*I + 1 = L<\/pre>\n
So the above property is proved using Handshaking Lemma, let us discuss one more interesting property.<\/p>\n[ad type=”banner”]\n
2) In Binary tree, number of leaf nodes is always one more than nodes with two children.<\/strong><\/em><\/p>\n
   L = T + 1\r\nWhere L = Number of leaf nodes\r\n      T = Number of internal nodes with two children<\/pre>\n
Proof:<\/strong>
\nLet number of nodes with 2 children be T. Proof can be divided in three cases.
\nCase 1:<\/em><\/strong> There is only one node, the relationship holds
\nas T = 0, L = 1.
\nCase 2:<\/em><\/strong> Root has two children, i.e., degree of root is 2.<\/p>\n
   Sum of degrees of nodes with two children except root + \r\n   Sum of degrees of nodes with one child + \r\n   Sum of degrees of leaves + Root's degree = 2 * (No. of Nodes - 1)   \r\n\r\n   Putting values of above terms,\r\n   (T-1)*3 + S*2 + L + 2 = (S + T + L - 1)*2\r\n\r\n   Cancelling 2S from both sides.\r\n     (T-1)*3 + L + 2 = (S + L - 1)*2\r\n     T - 1 = L - 2\r\n     T = L - 1<\/pre>\n
Case 3: <\/strong><\/em>Root has one child, i.e., degree of root is 1.<\/p>\n
   Sum of degrees of nodes with two children + \r\n   Sum of degrees of nodes with one child except root + \r\n   Sum of degrees of leaves + Root's degree = 2 * (No. of Nodes - 1)   \r\n\r\n   Putting values of above terms,\r\n   T*3 + (S-1)*2 + L + 1 = (S + T + L - 1)*2\r\n\r\n   Cancelling 2S from both sides.\r\n     3*T + L -1 = 2*T + 2*L - 2\r\n     T - 1 = L - 2\r\n     T = L - 1<\/pre>\n
Therefore, in all three cases, we get T = L-1.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Handshaking Lemma and Interesting Tree Properties – Tree – Handshaking lemma is about undirected graph. In every finite undirected graph number of vertices <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80139,83787],"tags":[80477,80482,80483,80479,80481,80484,80480,80478],"class_list":["post-26983","post","type-post","status-publish","format-standard","hentry","category-binary-tree-divide-and-conquer","category-handshaking-lemma","tag-handshake-lemma-proof","tag-handshaking-lemma-definition","tag-handshaking-lemma-directed-graph","tag-handshaking-lemma-proof-by-induction","tag-handshaking-problem","tag-handshaking-theorem-definition","tag-handshaking-theorem-directed-graph","tag-handshaking-theorem-in-discrete-mathematics"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26983","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26983"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26983\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26983"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26983"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26983"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}