Sign up ×
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.

This question already has an answer here:

I believe the answer is $\frac12(n-1)^2$, but I couldn't confirm by googling, and I'm not confident in my ability to derive the formula myself.

share|cite|improve this question

marked as duplicate by Douglas S. Stones, Amzoti, TMM, Martin, Micah May 19 '13 at 19:28

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.

So you think a clique of $2$ vertices has exactly $\frac12$ edges? – Chris Eagle Sep 20 '12 at 13:20
Oh yeah, how silly. Good thing I checked. – MikeFHay Sep 20 '12 at 13:21
$\frac12 (n^2 - n)$? – MikeFHay Sep 20 '12 at 13:25
I think I would upvote this question if it included your (as Chris points out, incorrect) derivation. – Ben Millwood Sep 20 '12 at 13:26
@MikeL: I think I would upvote this question if you made much effort, then :P – Ben Millwood Sep 20 '12 at 13:37

2 Answers 2

up vote 3 down vote accepted

A clique has an edge for each pair of vertices, so there is one edge for each choice of two vertices from the $n$. So the number of edges is:


Edit: Inspired by Belgi, I'll give a third way of counting this! Each vertex is connected to $n-1$ other vertices, which gives $n(n-1)$ times that an edge is joined to a vertex. As each edge is joined to exactly two vertices, there must be $\frac{1}{2}n(n-1)$ edges.

share|cite|improve this answer
That makes sense, thank you. – MikeFHay Sep 20 '12 at 13:31
nice, I wish I could upvote again :) – Belgi Sep 20 '12 at 13:49

Another way to calculate what Matt said it to this: number the vertices from $1$ to $n$, and consider the graph with $n$ vertices but with no edges.

Take the first vertice: it has vertics to the other $n-1$ vertices, connect those $n-1$ vertices

Take the second vertice: it has vertics to the other $n-1$ vertices - but one of them is already connected - connect the other $n-2$

do this untill the last vertice. you get that you connected $(n-1)+(n-2)+...+1$ vertices which is an arithmetic proggrestion whose sum is $\frac{1}{2}(n-1)n$

share|cite|improve this answer
Yes, I think this is how I once learned it. Thank you. – MikeFHay Sep 20 '12 at 13:33

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