1
$\begingroup$

I'm looking at 2 versions of textbook for structural induction and I just can't understand structural induction and how to draw the rooted trees from it. Does anyone have a good resource or can help me lighten up my brain so that I can understand it?

Maybe it's better if I give an example... How would you approach this problem? (I know what rooted trees are)

A full binary tree is a graph defined through the following recursive definition. Basis step: A single vertex is a full binary tree. Inductive step: If T1 and T2 are disjoint full binary trees with roots r1, r2, respectively, the the graph formed by starting with a root r, and adding an edge from r to each of the vertices r1; r2 is also a complete binary tree.

Use structural induction to show that l(T) the number of leaves of a complete binary tree T, is 1 more than i(T), the number of internal vertices of T. 2

  • 0
    Maybe if we knew the textbooks we could see what you're having trouble understanding, and find another way to say it.2012-11-20
  • 0
    Discrete Mathematics and Its applications 7th edition Rosen and Discrete and combinatorial mathematics - an applied introduction 5th ed Grimaldi2012-11-20
  • 0
    Check my edit please!2012-11-20

1 Answers 1

1

The base for the induction is the tree that's just a single vertex. That tree has one leaf and no internal vertices, so the statement is true for that tree.

Now let $T$ be a tree that's not just a single vertex, and make the induction hypothesis that the statement is true for all trees smaller than $T$. We get $T$ from trees $T_1$ and $T_2$, and we are assuming the statement is true for them. How many leaves does $T$ have? The leaves of $T$ consist of the leaves of $T_1$, together with the leaves of $T_2$, so $$\ell(T)=\ell(T_1)+\ell(T_2)\tag1$$ How many internal vertices does $T$ have? The internal vertices of $T$ are the internal vertices of $T_1$, the internal vertices of $T_2$, and the roots of $T$, so $$i(T)=i(T_1)+i(T_2)+1\tag2$$ By the induction hypothesis, $$\ell(T_1)=i(T_1)+1{\rm\ and\ }\ell(T_2)=i(T_2)+1\tag3$$ Put (3) into (1) to get $$\ell(T)=i(T_1)+i(T_2)+2\tag4$$ Now comparing (2) and (4), $\ell(T)=i(T)+1$, as we were to prove.

Let me know if there's anything that needs explaining (after you've tried to work through it on your own).

  • 0
    From your (2), why is the +1 added, doesn't that mean internal vertices are one more instead of leaves being one more than the internal vertices? It is related at #3, but confused me how you came up with that +1 there2012-11-20
  • 0
    (2) is just counting the internal vertices of $T$ --- the $+1$ is the root of $T$. Its presence in (2) has nothing to do with the relation between $\ell$ and $i$.2012-11-20
  • 0
    So even the root counts as an internal vertice?2012-11-20
  • 0
    I think the root must count as an internal vertex (provided it isn't a leaf). Think about a tree with just 3 vertices: the root, and two leaves. For the number of leaves, 2, to be one more than the number of internal vertices, you have to count the root as an internal vertex.2012-11-20
  • 0
    @Aaron: Yes: *internal vertex* here means *non-leaf*.2012-11-20