Answer to Question #274998 in Discrete Mathematics for V.kathiravan

Question

Show that a tree with n vertices has exactly n-1 edges

Answer 1

Consider the tree with n vertices. To Prove: The number of edges will be n-1.

Assume P(n): Number of edges = n-1 for the tree with n vertices. n will be natural number.

P(1): For one node, there will be zero edges, since there is no other node to connect with.

P(2): For two nodes, Number of edges = n-1 = 2-1 = 1, since one edge is sufficient to connect two nodes in a tree.

...

Assume P(n) is true, i.e. for n number of vertices in a tree, number of edges = n-1.

Now, For P(n+1),

the number of edges will be (n-1) + number of edges required to add (n+1)th node.

Every vertex that is added to the tree contributes one edge to the tree.

Thus, the number of edges required to add (n+1)th node = 1.

Thus the total number of edges will be (n - 1) + 1 = n -1+1 = n = (n +1) - 1.

Thus, P(n+1) is true.

So, Using Principle of Mathematical Induction, it is proved that for given n vertices, number of edges = n - 1.