Prove that in a full binary tree with n vertices, the number of pendant vertices is (n+1)/2.
1 Answer

In a full binary tree, only one vertex, namely, the root is of even degree (namely 2) and each of the other (n-1) vertices is of odd degree (namely 1 or 3.)

Since the number of vertices of odd degree in an undirected graph is given even, (n-1) is even.

$\therefore n$ is odd.

Now let p be the number of pendant vertices of the full binary tree.

$\therefore$ The number of vertices of degree 3= n-p-1

$\therefore$ The sume of the degrees of all the vertices of the tree

$\hspace{2.6cm}=1 \times 2+ p \times (n-p-1) \times 3 \\ \hspace{2.5cm}=3n-2p-1$

$\therefore$ Number of edges of the tree = $\dfrac12(3n-2p-1)$

$\hspace{2.6cm}(\because \text{each edge contributes 2 degrees)}$

But the number of edges of a tree with n vertices=n-1 (by an earlier property)

$\therefore \hspace{2cm} \dfrac12(3n-2p-1)=n-1$

$i.e., \hspace{1.6cm} 3n-2p-1=2n-2$

$i.e., \hspace{1.6cm} 2p=n+1 \ \ or \ \ p=\dfrac{n+1}{2}.$

Please log in to add an answer.