Question

Prove that in a binary tree the number of vertices is always odd

Answer 1

A complete binary tree has an odd number of vertices (nodes).

At level 0, (at the root), we have 1 node.
At level 1, we have  2 nodes.
At level 2, we have  2*2 = 4 nodes.
At depth or height n-1, we have 2ⁿ⁻¹ nodes.

Total = 1 + 2 + 2² + 2³ + .... + 2ⁿ⁻¹ =  2ⁿ - 1
Hence it is an odd number.

At all other depths other than at level 0, we have even number of nodes. At level 0, we have 1 node. So total number is always an odd number.

Answer 2

Answer:

let n be the no. of vertices in a binary tree.

since, there is exactly one vertex of even degree.

therefore,all the remaining (n-1) vertices are of odd degrees.

since, the no. of the odd degree vertices in a graph is always even.

implies that (n-1) is even.

Hence, n is odd.