1. Mathematical Induction

Hi guys,

Had this question today in my final but dont know how to complete, any suggestions would be appreciated.

Using induction proof to show that every tree has one more node than it has edges.

That is, to prove the statement:

If
T is a tree, and T has n nodes and e edges, then

n = e + 1.

2. Originally Posted by extatic
Hi guys,

Had this question today in my final but dont know how to complete, any suggestions would be appreciated.

Using induction proof to show that every tree has one more node than it has edges.

That is, to prove the statement:

If
T is a tree, and T has n nodes and e edges, then

n = e + 1.
(I am presuming you are talking about connected trees...? A disconnected tree could have n nodes and zero edges...)

Induct on the number of edges. If it has one edge it must have 2 nodes, one at each end of the edge.

Assume true for all trees with $r$ edges. Then the number of nodes is $r+1$ on such a tree.

Let $\Gamma$ be a tree with $r+1$ edges. Then it contains a subtree with $r$ edges (just delete one of the bottom-most edges and the ONE node at its tip). This tree, $\Gamma^{\prime}$, has $r+1$ nodes, but as we deleted ONE node from $\Gamma$ this means that $\Gamma$ must have $r+2$ nodes.

As $e=r+1$ we have that $n=r+2 = (r+1)+1 = e+1$ as required.

Is there anything you specifically do not understand in this?...

3. Thankyou Swlabr, your response is awesome!