Show that a tree with n vertices has exactly n-1 edges
The Answer to the Question
is below this banner.
Here's the Solution to this Question
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.