Question

Prove

\({\bf{a)}}\)part \(\left( {ii} \right)\) of Theorem \(4\).

\({\bf{b)}}\)part \(\left( {{\bf{iii}}} \right)\) of Theorem \(4\).

Short answer

1. Theorem 3 gives us \({\bf{n = m i + 1}}\) with notations having their usual significance. This proves the first part. The number of leaves is the difference between the total number of vertices in the tree and the number of internal vertices, i.e. \({\bf{l = n - i = }}\left( {{\bf{m i + 1}}} \right){\bf{ - i = }}\left( {{\bf{m - 1}}} \right){\bf{ i + 1}}\).

2. Using the previous answer, \({\bf{l = (m - 1)i + 1}} \Rightarrow {\bf{i = (l - 1)/(m - 1)}}\) and \({\bf{n = mi + 1 = m \times }}\frac{{{\bf{l - 1}}}}{{{\bf{m - 1}}}}{\bf{ + 1 = }}\frac{{{\bf{ml - 1}}}}{{{\bf{m - 1}}}}\).

Step-by-step solution

(a) Using theorem \(4\left( {{\bf{ii}}} \right)\)

Theorem 3 gives us \({\bf{n = m i + 1}}\) with notations having their usual significance. This proves the first part. The number of leaves is the difference between the total number of vertices in the tree and the number of internal vertices, i.e. \({\bf{l = n - i = }}\left( {{\bf{m i + 1}}} \right){\bf{ - i = }}\left( {{\bf{m - 1}}} \right){\bf{ i + 1}}\).

(b) Using theorem \({\bf{4}}\left( {{\bf{iii}}} \right)\)

Using the previous answer, \({\bf{l = (m - 1)i + 1}} \Rightarrow {\bf{i = (l - 1)/(m - 1)}}\) and \({\bf{n = mi + 1 = m \times }}\frac{{{\bf{l - 1}}}}{{{\bf{m - 1}}}}{\bf{ + 1 = }}\frac{{{\bf{ml - 1}}}}{{{\bf{m - 1}}}}\).