Standard 7: Graph Traversal 1: Graphs and Trees

The base case is a binary tree consisting of one vertex and no edges. That vertex is a leaf. So there are $1 = 2^0 = 2^d$ leaves.

For the inductive case, by the inductive definition of a binary tree, it is of the form of a root with at most two children, each of which is the root of a binary tree. Suppose without loss of generality that the heights of these subtrees are $k_1 \leq k_2$. By inductive hypothesis, the number of leaves in each subtree is at most $2^{k_1}$ and $2^{k_2}$ respectively. Each child's binary tree is of height at most $d-1$, so each child's tree has at most $2^{d-1}$ leaves. The leaves of the new tree consist of all leaves of the old tree, so there are at most $2^{d-1} + 2^{d-1} = 2^d$ leaves.

Here is one example.

Here, there are two $3$-cycles. Each vertex is part of one of the $3$-cycles. But there is a single edge from a vertex in the first cycle to a vertex in the second. Vertices in the first can reach the second, but not vice versa.

To pass, a solution must follow the course requirements for writing and proofs. It must also follow the inductive proof.

To pass, the solution should use the inductive definition of a binary tree as either a single node, or a root connected to one or two binary trees. It should clearly apply the inductive hypothesis.

The numerical rubric for this problem is:

• 4 (Pass, Near-Perfect): correct, clear, and with brief explanations. Perfectly follows requirements of a proof by induction using the definition of a binary tree. No incorrect statements or skipped steps. May state without proof that the child trees have height at most $2^{d-1}$. May state without proof that the leaves of the new tree consist of the union of the leaves of the old trees.
• 3 (Pass, Proficient): correct proof by induction, clear steps, brief. May have minor arithmetic erros if the correct meaning is clear. Should mention that the leaves of the new tree are the union of the leaves of the old trees, although if everything else is perfect, this comment can be omitted. May use induction on the height $d$ of the binary tree, if everything is done perfectly.
• 2 (Fail, Progress): may fail to correctly use the inductive definition of binary tree. May skip or omit important steps mentioned above. May have an arithmetic error that alters the meaning of the solution.
• 1 (Fail, Wrong Track): May not correctly use a proof by induction structure, or may not attempt to use induction on the height of the tree or on the

To pass, a solution must give a directed graph that is clear and easy to understand (preferably as a clear diagram). It must correctly answer the question. The explanation can be quite brief as long as the graph is correct.

The numerical rubric for this problem is:

• 4 (Pass, Near-Perfect): correct, clear, well-presented, and with a brief, correct explanation.
• 3 (Pass, Proficient): correct, and with a sufficient explanation, but perhaps not as well presented or with minor errors in the explanation.
• 2 (Fail, Progress): may give an incorrect graph, e.g. some vertex is not part of a cycle, or the graph actually is strongly connected. May give a graph that is unclear or ambiguous. May give a very wrong explanation.
• 1 (Fail, Wrong Track): May not give an understandable graph or an undirected graph. May misuse definitions of strongly connected or cycle.