- #1

- 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.