- #1
TheMathNoob
- 189
- 4
Homework Statement
Show that every 2-tree(Definition 3.2) with n internal nodes has n+1 external nodes
Homework Equations
A 2 tree is a tree which nodes have 2 children or no children.
Internal nodes are nodes which have two children
external nodes are leafs.
The Attempt at a Solution
Proof
base case
n=1
Internal nodes=1
external nodes=2
Inductive step
Inductive hypothesis: Let k internal nodes have k+1 external nodes
so k+1 internal nodes will have (k+1)+1 external nodes.