Proof

Since, A tree Graph is connected it must be a supergraph of K[sub]2[/sub]

So let us start with the base case of K[sub]2[/sub]

Here, the number of leaves are 2 and the number of internal vertex are 0

So m(number of internal vertices) = n(number of leaves) - 2 in this case

Now, every time we make a supergraph of it such that the property of the tree is preserved: We add 2 vertices connected to one of the leaves.

Now, the number of internal vertices is increased by one (since the old leaf has now two vertices connected to it).

We have two new leaves, but one previous leaf is now an internal vertex. So, the number of leaves has also increased by one.

So, m[sub]new[/sub] = m[sub]old[/sub] + 1

and n[sub]new[/sub] = n[sub]old[/sub] + 1

Therefore, m[sub]new[/sub] = m[sub]old[/sub] + 1 = (n[sub]old[/sub] - 2) + 1 = (n[sub]old[/sub] + 1) - 2 = n[sub]new[/sub] - 2

Thus, by induction the number of vertices that have degree 3 is equal to (n-2) always in such a tree

]]>many have degree 3?

how can i show this?

]]>