I have a question about how to apply induction proofs over a graph. Let's see for example if I have the following theorem:
Proof by induction that if T has n vertices then it has n-1 edges.
So what I do is the following, I start with my base case, for example:
This graph is a tree with two vertices and on edge so the base case holds.
Let's assume that we have a graph T which is a tree with n vertices and n-1 edges (Induction Hypothesis) Now I take a new vertex that is not connected to the tree that I will call it v'. If I add this v' to T then I will have to connect it with any vertex that is on T by an edge to form the new graph T'. By IH hypothesis T has n vertices and n-1 edges, and by adding this new vertex I will end up with n+1 vertices and n edges. As we see the addition of this new vertex v' with its correspondent edge will not form a cycle, so T' will also be a tree.
Is it my induction proof fine? and if its not, then how it will be a sound induction proof?