91Ó°ÊÓ

Draw all nonisomorphic binary trees having four vertices.

Draw all nonisomorphic full binary trees having nine vertices.

Draw a graph having the given properties or explain why no such graph exists. Acyclic; four edges, six vertices

Show that the height \(h\) of an \(n\) -vertex balanced binary tree satisfies \(h=O(\lg n) .\) This result shows that the worst-case time to search in an \(n\) -vertex balanced binary search tree is \(O(\lg n)\)

Construct an optimal Huffman code for the set of letters in the table. $$ \begin{array}{cr|cr} \hline \text { Letter } & \text { Frequency } & \text { Letter } & \text { Frequency } \\ \hline \text { I } & 7.5 & \text { C } & 5.0 \\ \text { U } & 20.0 & \text { H } & 10.0 \\ \text { B } & 2.5 & \text { M } & 2.5 \\ \text { S } & 27.5 & \text { P } & 25.0 \\ \hline \end{array} $$

Explain why if we allow cycles to repeat edges, a graph consisting of a single edge and two vertices is not acyclic.

Explain why a forest is a union of trees.

Show that a tree is a planar graph.

If a forest \(F\) consists of \(m\) trees and has \(n\) vertices, how many edges does \(F\) have?

Show that any tree with two or more vertices has a vertex of degree 1 .