I would like to proof the following theorem by induction:
Theorem: If G is a graph that is not complete, then it is possible to add at least one edge to it.
Inductive proof: Base case: Assume we have a graph G(v,e), and v=4 if we have a graph like the following:
a------b | | | | c------d
the graph is not complete so it is possible to add at least one edge from a-d or from b-c; so the base case holds
Consider now a graph G'(v,e) with v>4 that is not complete so according to our theorem would be possible to add at least one edge between any pair of vertices, this would be our Induction Hypothesis.
Now I would take another vertex v'and I would like to join this to our original graph G'(v,e) to form G''(v',e'), it can occur two cases:
Asssume that v' does not have an outgoing edge so it is not connected to G', because of this at least one edge could be added to connect it to another vertex, but as long as I am not connecting v'to all the other vertices of G' then the graph is still not complete and by IH I could be able to add at least another edge.
Assume that v'is connected to another vertex in G', this additional edge will not make G'' complete, because this vertex would need to be connected to all the other vertices of G', meaning that at least I can add one edge more, and according to our IH because G'was not complete, the addition of this edges from v' to G'would still not make G'' complete; leaving space for adding at least one additional edge to G'.
Is my proof by induction correct? Thanks