Question

Draw \({{\bf{B}}_{\bf{k}}}\) for \({\bf{k = 0,1,2,3,4}}\).

Short answer

Therefore, the draw of \({{\bf{B}}_{\bf{k}}}\) for \({\bf{k = 0,1,2,3,4}}\) is shown below.

Step-by-step solution

General form

Principle of Binomial trees: The binomial trees \({{\bf{B}}_{\rm{i}}}\), \({\bf{i = 0,1,2,}}...{\bf{,}}\) are ordered rooted trees defined recursively:

Basis step: the binomial tree \({{\bf{B}}_0}\) is the tree with a single vertex.

Recursive step: Let k be a nonnegative integer. To construct the binomial tree \({{\bf{B}}_{{\bf{k + 1}}}}\), add a copy of \({{\bf{B}}_{\bf{k}}}\) to a second copy of \({{\bf{B}}_{\bf{k}}}\) by adding an edge that makes the root of the first copy of \({{\bf{B}}_{\bf{k}}}\) the leftmost child of the root of the second copy of \({{\bf{B}}_{\bf{k}}}\).

Draw the rooted trees

Given that, \({\bf{k = 0,1,2,3,4}}\).

Draw \({{\bf{B}}_{\bf{k}}}\).

Since, \({{\bf{B}}_0}\)contains a single vertex.

Then,\({{\bf{B}}_1}\) contains an edge between two single vertices and one of the vertices has to be the root.

\({{\bf{B}}_2}\) contains two copies of \({{\bf{B}}_1}\) with an edge from the root of one copy to the root of the other copy.

Note: you then also need to place the root of the left copy at level 1 along with the rest of the copy.

\({{\bf{B}}_3}\)contains two copies of \({{\bf{B}}_2}\) with an edge from the root of one copy to the root of the other copy.

\({{\bf{B}}_4}\)contains two copies of \({{\bf{B}}_3}\) with an edge from the root of one copy to the root of the other copy.

The graph is shown below.

Conclusion: The above graph represents the \({{\bf{B}}_{\bf{k}}}\) for \({\bf{k = 0,1,2,3,4}}\).