3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ the formula $|V(K_{n+1})|-v = n (K_{n})$ is either not well written, or needs more explanation $\endgroup$
    – Exodd
    Apr 25, 2021 at 11:57
  • $\begingroup$ 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. $\endgroup$ Apr 25, 2021 at 15:01

2 Answers 2

1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .