1.19

Step 1: Show that the statement holds for the basis case $n=1$

$E(n)=n-1$

$E(1)=1-1=0$. 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.

$E\left(n+1\right)=n+1-1$

$\Leftrightarrow E(n)+1=n$ When adding one node to a tree one edge is added as well

$\Leftrightarrow n-1+1=n$

$\Leftrightarrow n=n$

QED

Back to Chapter 1.