Question

Either draw a full \({\bf{m - }}\)ary tree with \(76\) leaves and height \(3\), where \({\bf{m}}\) is a positive integer, or show that no such tree exists.

Short answer

Such a graph exists

Step-by-step solution

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

Theorem\({\bf{4}}\left( {{\bf{iii}}} \right)\): A full\({\bf{m - }}\)ary tree with\({\bf{l}}\)leaves has\({\bf{n = }}\frac{{{\bf{ml - 1}}}}{{{\bf{m - 1}}}}\)vertices and\({\bf{i = }}\frac{{{\bf{l - 1}}}}{{{\bf{m - 1}}}}\)internal vertices.

Given: the full m-ary tree has 76 leaves and height 3.

\(l = 76\).

By theorem\(4\left( {iii} \right)\), the number of internal vertices is:

\(i = \frac{{l - 1}}{{m - 1}} = \frac{{76 - 1}}{{m - 1}} = \frac{{75}}{{m - 1}}\)

Drawing the root

Since the number of internal vertices needs to be an integer,\(m - 1\)needs to divide 75. Since 5 divides 75, we will check if there exists such a full m-ary tree when\(m - 1 = 5\)or equivalently\(m = 6\).

Let us start withdrawing the root and its 6 children. Let us also assume that each of those 6 children are not leaves and thus draw 6 children for those 6 vertices.

Adding the leaves

We then note that the resulting three contains\(6 \times 6 = 36\)leaves at height 2 .

If we add 6 children to one of those leaves on height 2 by, then the number of leaves increase by 5 (6 children and the original leave is no longer a leave). Since 76 is 40 higher than 36 and since\(\frac{{40}}{5} = 8\), we need to add six children to 8 of the vertices at height 2 .

The resulting graph should then contain\({\bf{36 + 40 = 76}}\)leaves.

Such a possible graph is given in the image below.