Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i'm studing graphs in algorithm and complexity, (but i'm not very good at math) as in title, why a complete graph has $\frac{n(n-1)}{2}$ edges? and how this is related with combinatorics?

share|improve this question

4 Answers 4

up vote 14 down vote accepted

A simpler answer without binomials: A complete graph means that every vertex is connected with every other vertex. If you take one vertex of your graph, you therefore have $n-1$ outgoing edges from that particular vertex.

Now, you have $n$ vertices in total, so you might be tempted to say that there are $n(n-1)$ edges in total, $n-1$ for every vertex in your graph. But this method counts every edge twice, because every edge going out from one vertex is an edge going into another vertex. Hence, you have to divide your result by 2. This leaves you with $n(n-1)/2$.

share|improve this answer

A complete graph has an edge between any two vertices. You can get an edge by picking any two vertices.

So if there are $n$ vertices, there are $n$ choose $2$ = ${n \choose 2} = n(n-1)/2$ edges.

Does that help?

share|improve this answer

$\frac{n(n-1)}{2} = \binom{n}{2}$ is the number of ways to choose 2 unordered items from n distinct items.

In your case, you actually want to count how many unordered pair of vertices you have, since every such pair can be exactly one edge (in a simple complete graph).

suppose $(v,u)$ is an edge, then v can be any of the vertices in the graph - you have n options for this. u can be any vertex that is not v, so you have (n-1) options for this. the problem is that you counted each edge twice - one time as $(u,v)$ and one time as $(v,u)$ so you need to divide by two, and then you get that you have $\frac {n(n-1)}{2}$ edges in a complete simple graph.

share|improve this answer

$\frac{n(n-1)}{2}$ comes from simple counting argument. You could directly say that every edge is obtained by choosing a pair of vertices so the number is $C(n,2) = \frac{n(n-1)}{2}$ or you could take the other way of counting. Label the vertices $1,2, \ldots ,n$. The first vertex is now joined to $n-1$ other vertices. The second vertex has already been joined to vertex $1$ and hence has to be joined to the remaining $n-2$ vertices and in general the $k^{th}$ vertex has already been joined to the previous $k-1$ vertices and hence has to be joined to the remaining $n-k$ vertices. So the total number of edges is given by $(n-1) + (n-2) + \ldots 2 + 1 = \frac{n(n-1)}{2}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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