Proof verification: Prove that a tree with n vertices has n-1 edges

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.

What seems missing from the proof is:

• After the $n$-th vertex is added, how do we know there exists some "unused" vertex $v$ which is adjacent to a "used" vertex?

• How do we know that $v$ is not adjacent to multiple "used" vertices?

• How do we know that this algorithm will terminate, having used all the vertices?

Also note that not all trees are rooted (i.e., have a root vertex), but we can distinguish an arbitrary vertex to make it rooted.