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:

|      |
|      |

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


Your proof by induction seems to be a bit fishy. Also, why would you attempt a proof by induction in the first place? The theorem is an immediate consequence of the definition of complete graph: $G$ is not complete $\iff$ not (for every two distinct vertices $a,b$ of $ G$, there is an edge $ab$) $\iff$ There exist two distinct vertices $a,b$ of $G$ such that there is no edge $ab$ $\iff$ There exist two distinct vertices $a,b$ of $G$ such that it is possible to add an edge $ab$.

  • $\begingroup$ Thanks for your comment @Hagen von Eitzen, but is it possible to proof it by induction? $\endgroup$ – Lila May 9 '16 at 23:00
  • 1
    $\begingroup$ @Lila It's a bit hard to really use induction when one merely proves a reformulation of a definition. Would you prove $n^2=n\cdot n$ by induction? Could you even do it without accidentally using the straight fact? $\endgroup$ – Hagen von Eitzen May 10 '16 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.