written 7.9 years ago by | modified 2.6 years ago by |
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}.$