1.19
Step 1:
Show that the statement holds for the basis case
[math]\displaystyle{ n = 1 }[/math]
-
[math]\displaystyle{ E(n) = n - 1 }[/math]
- [math]\displaystyle{ E(1) = 1 - 1 = 0 }[/math] . A tree with one node has zero edges
Step 2:
Assume that that summation is true up to
n
.
Step 3:
Show that on the assumption that the summation is true for
n
, it follows that it is true for
n + 1
.
-
[math]\displaystyle{ E\left(n + 1\right) = n + 1 - 1 }[/math]
-
[math]\displaystyle{ \Leftrightarrow E(n) + 1 = n }[/math]
When adding one node to a tree one edge is added as well
-
[math]\displaystyle{ \Leftrightarrow n -1 + 1 = n }[/math]
-
[math]\displaystyle{ \Leftrightarrow n = n }[/math]
QED
Back to
Chapter 1
.
