3
$\begingroup$

This question already has an answer here:

Given a complete graph of n vertices $K_n$ (has all possible edges – one edge between pair of vertices). Use counting to find a formula in $n$ for the number of edges in the graph.

I know that the formula is $\frac{n(n-1)}{2}$ (or at least that's what I think it is from what Wikipedia said.

Though I am not sure how to actually start deriving the formula to come to that conclusion. Any guidance would be great.

$\endgroup$

marked as duplicate by Martin Sleziak, user91500, miracle173, Harish Chandra Rajpoot, Jendrik Stelzner Jan 12 '16 at 9:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

For complete graphs you could use

$$ \dbinom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}. $$

$\endgroup$
4
$\begingroup$

Every edge is uniquely determined by its two terminal vertices. How many sets of two elements exist? there are $n$ options for the first vertex and $n-1$ options for the second vertex, so $n\cdot(n-1)$. Only we counted the pair $(u,v)$ and $(v,u)$ as different, so we must divide by two. So there are $\frac{n(n-1)}{2}$ subsets of two vertices, each of these defines one of the edges. So there are $\frac{n(n-1)}{2}$ edges in the complete graph on $n$ vertices.

$\endgroup$
2
$\begingroup$

There are n people in a party. All shake hands. How many shakes are there? This is the same problem.

Each of the $n$ people shakes hands with the other $n-1$ for a total of $n (n-1)$ shakes, but wait! when you and I shake hands it is only one shake no two, so divide by two. Total $n(n-1)/2$.

$\endgroup$

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