Graph theory induction

Question

Prove by induction that if $G$ is a complete graph, which has n vertices, then the network $G$ has $n(n − 1)/2$ edges.

How do we go about induction with networks?

Answer 1

The base case is trivial.

Imagine that we have a complete graph with $n-1$ vertices, then under the induction hypothesis, one must have $\frac{(n-1)(n-2)}{2}$ edges. Let's add one more vertex that is connected to all other $n-1$ vertices. This results in $n-1$ supplemental edges, so in total $$\frac{(n-1)(n-2)}{2} + n-1 = \frac{(n-1)(n-2) + 2(n-1)}{2} = \frac{(n-1)(n-2+2)}{2} = \frac{n(n-1)}{2}$$ edges with $n$ vertices.