Proof verification: Prove that a tree with n vertices has n-1 edges This question is not a duplicate of the other questions of this time. I want to ask is how strong is the following proof that I am going to give from an examination point of view?

Proof:

Consider a tree $T$ with $n$ vertices. Let us reconstruct the tree from the root vertex. 
When the first root vertex has been added, the number of edges is zero. After the root vertex, every vertex that is added to the construction of $T$ contributes one edge to $T$.
Adding the remaining $n-1$ vertices to the construction of $T$, after the root vertex, will add $n-1$ edges. 
Therefore, after the reconstruction of $T$ is complete, $T$ will have $n$ vertices and $n-1$ edges.
Hence Proved.

Is this a sound proof at all?
 A: 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.
A: 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.
