Complete graph induction

Question

I'm new to both subjects and also this forum, so any help would be greatly appreciated.

Proof by induction if that $G$ is a complete graph with n vertices, then the number of edges of $G$ is $n (n - 1) / 2$.

Thanks in advance.

Answer 1

Hint: an induction proof has two steps.

Base case: Prove the statement true for the simplest case possible. In this case, a graph with $n=1$ vertex is the simplest. In this case, the formula $\frac{(1)(1-1)}{2}=0$ works, but why?

Induction step: We can assume that the formula works for any complete graph with $1,2,\ldots,n$ vertices (this is called the "induction hypothesis", which we will use later on).

Now we need to show that the for a complete graph with $n+1$ vertices, the formula holds; i.e. the number of edges is $\frac{(n+1)(n+1-1)}2=\frac{(n+1)(n)}2$. If we delete one of the vertices, we now have a graph with $n$ vertices, so we already know that this graph has $\frac{n(n-1)}{2}$ edges by the induction hypothesis. How many edges did we lose when we deleted one of the vertices? We can use this to determine how many edges a complete graph with $n+1$ vertices should have.