[Math] show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$.

discrete mathematicsproof-writing

I have to provide a structural proof for this:
show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$.

I have the following, and I'm wondering if I'm doing this correctly. I have no idea what the inductive hypothesis is here… Thanks in advance!

The set of all full binary trees $B$ can be defined recursively as:

$T_0$ is in $B$ such that $T_0$ has $i(T_0) = 1$ number of internal vertices and $l(T_0) = 2$ number of leaves.

For any tree $T_n$ in $B$, $T_{n+1}$ is in $B$ such that $T_{n+1}$ has $i(T_{n+1}) = i(T_n) + 1$ number of internal vertices, and $l(T_{n+1}) = l({T_n}) + 1 $ number of leaves.

Structural Inductive Proof:

Base Step:

Tree $T_0$ has 1 internal vertex and 2 leaves. so the number of leaves is 1 more than the number of internal vertices.

Inductive Step:

Since, each tree in $B$ is generated from the base case by adding 1 to the number of leaves and 1 to the number of vertices, and since the base tree in $B$ has 1 more leaf than internal vertex, every full binary tree has 1 more leaf than internal vertex.

Best Answer

As Andreas Blass said, you need to start with an actual recursive definition of full binary tree. What’s the smallest, simplest full binary tree? It’s the tree with a single vertex and no edges; take that as your starting point. If you have a full binary tree, how do you build the next larger one? You attach a pair of edges and vertices to each leaf; that’s your construction step. Put those together (and add the usual limiting statement), and you have your definition:

  1. The tree with one vertex and no edges is a full binary tree.
  2. Suppose that $T$ is a full binary tree with leaves $v_1,\dots,v_n$. Let $u_1,\dots,u_n$ and $w_1,\dots,w_n$ be $2n$ new vertices. Add these vertices to $T$, and for $k=1,\dots,n$ add edges from $v_k$ to $u_k$ and $w_k$; the resulting graph is a full binary tree.
  3. A graph is a full binary tree if and only if it is required by clauses (1) and (2) to be one.

Now see if you can prove your theorem by structural induction from this definition. Certainly the induction gets off the ground easily enough: The one-vertex graph has one leaf and no internal vertices, and $1=0+1$.

Related Question