# Prove that a complete graph with $n$ vertices has $\frac{n(n-1)}{2}$ edges using induction

Let us assume a complete graph $$K_{n}$$
Base case: Let $$n = 1$$, in such case, we do not have any edges since this is an isolated vertex. By the formula we get $$\frac{1(1-1)}{2} = 0$$. For the base case, claim holds.

Let us assume that claim holds for $$K_{n}$$ and that $$n \geq 1$$, Prove that claim holds for $$n+1$$ Let us have $$K_{n+1}$$ and remove a vertex $$v\in V(K_{n+1})$$, therefore we get that $$|V(K_{n+1})|-v = n (K_{n})$$, which holds by the $$IH$$. Let us add back vertex v, we need to make sure graph still remains as a complete graph, therefore, while adding the $$n+1$$'th vertex (v), we need to have $$deg(v) = n$$, so number of edges will be $$\frac{n(n-1)}{2}+\frac{2n}{2} = \frac{n(n+1)}{2}$$, which means claim holds for $$K_{n+1}$$ as well. Therefore, claim must be true

Would this proof be accurate ? if not, why ? Thank you

• the formula $|V(K_{n+1})|-v = n (K_{n})$ is either not well written, or needs more explanation Apr 25, 2021 at 11:57
• I basically tried to mean that n+1 vertices - 1 vertex = n vertices, More explicitly, I mean if you delete vertex v from complete graph with n+1 vertices, you get complete graph with n vertices. Apr 25, 2021 at 15:01

Your proof is ok, but your induction step only gives a lower bound, if you want to be extremely precise.

You are saying, that the newly added vertex should have $$deg(v)=n$$, so at least $$n$$ new edges should be added as well, that connects $$v$$ to $$K_n$$. It is trivial that while forming $$K_{n+1}$$ no existing edge would be removed from $$K_n$$, but you might want to state that as well to be most precise.

The upper bound can be added easily to the proof, by stating the definition, that a complete graph is simple and undirected so there are at most $$n$$ new connections to the existing vertices.

But this proof also depends on how you have defined Complete graph. You might have a definition that states, that every pair of vertices are connected by a single unique edge, which would naturally rise a combinatoric reasoning on the number of edges. Your proof is more suitable if you have a differently stated, but equivalent definition, that enumerates properties of $$K_n=(V,E)$$: simply connected, undirected and $$\forall v \in V(K_n): deg(v)=n$$

Your proof is essentially correct. I think it would be easier to read if you used words instead of symbols in several places, and if you argued from $$n$$ to $$n+1$$ rather than starting from $$K_{n+1}$$ and removing a vertex.

Your base case argument is fine. Then I would write:

Suppose $$K_n$$ has $$n(n-1)/2$$ edges. To construct $$K_{n+1}$$ we add one new vertex and create $$n$$ new edges to connect it to the $$n$$ vertices already there. Then $$\frac{n(n-1)}{2}+n = \frac{n(n+1)}{2}$$ so the edge count is correct for $$K_{n+1}$$.