Define a cs130A tree to be a single leaf node or an internal node (the root) connected to two disjoint subtrees, which are themselves cs130A trees. Prove by induction that for all cs130A trees the number of edges is equal to (2 * the number of leaves) - 2.

Here is my work:

Let $n =$ the number of leaves

Base case:

$$n=1:2n - 2 = 0$$

Induction Hypothesis: $$2k-2= \text{the number of edges}$$

Induction Step: $$\text{for }k+1: 2(k+1)-2= ?$$

I got stuck in representing $2(k+1)-2$. I'm not how to do this induction step.


Consider a CS130A tree (call it $T$) with $n = k + 1$ leaves, where $k \geq 1$. Then since $T$ has at least two leaves, we know by definition of a CS130A tree that $T$ consists of a root node connected with two edges to two disjoint CS130A subtrees (call them $T_1$ and $T_2$). To count the total number of edges in $T$, all we need to do is count the edges connecting the root node to the two subtrees, and add that to the number of edges in each subtree.

Let $n_1, n_2 \geq 1$ be the number of leaves in $T_1, T_2$, respectively, so that $n = k + 1 = n_1 + n_2$. Note that $n_1, n_2 \leq k$, so we can apply the induction hypothesis to each subtree. Indeed, observe that: \begin{align*} \text{number of edges in } T &= 2 + (\text{number of edges in } T_1) + (\text{number of edges in } T_2) \\ &= 2 + (2n_1 - 2) + (2n_2 - 2) \\ &= 2(n_1 + n_2) - 2 \\ &= 2n - 2 \end{align*} as desired. $~~\blacksquare$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.