# Proving terminal vertices and total vertices of a full binary tree?

I am trying to make a proof by induction of the following theorem.

````If T is a full binary tree with i internal vertices, then T has i + 1 
terminal vertices and 2i + 1 total vertices. 
````

I have done this so far but I am just starting to understand proofs and am stuck about what to do next.

````Base Case:
    P(1): 1 internal vertex => 1+1 = 2 terminal vertices

Induction:
    Assume true: P(n): n internal vertices => n+1 terminal vertices
    Show true: P(n+1): n+1 internal vertices => (n+1)+1 = n+2 terminal vertices
````

After this I am unsure of how to proceed.

-

## 1 Answer

SKETCH of proof: Let $T$ be a full binary tree with $i+1$ internal vertices. Let $v$ be a terminal vertex of maximal height, and let $u$ be the parent of $v$. $T$ is full, so $u$ has two children; let $w$ be the other child. Let $T'$ be the tree that remains when you remove $v$ and $w$ from $T$. Verify that $T'$ has $i$ internal vertices, and therefore by the induction hypothesis $i+1$ terminal vertices. One of these terminal vertices is $u$. When you restore $v$ and $w$ to $T'$ to recover $T$, you gain one internal vertex ($u$), you lose one terminal vertex ($u$), and you gain two terminal vertices ($v$ and $w$). The net change in internal vertices from $T'$ to $T$ is $+1$, as is the net change in terminal vertices, so $T$ must have $(i+1)+1=i+2$ terminal vertices.

-

Verify that T′ has i internal vertices ... removing v and w turns u into a terminal vertex and thus reduces internals by -1 making i internals and i + 1 terminals? – wazy Oct 4 '12 at 23:32
You are right, I thought for some reason about complete binary trees – Belgi Oct 4 '12 at 23:52
@wazy: That’s right; and that means that $T$ must have had $i+2$ terminals. – Brian M. Scott Oct 5 '12 at 0:30
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 31, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9100232720375061, "perplexity_flag": "head"}