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.
How many edges are in a clique of n vertices?
-
0Provided you know the answer to be $\tbinom{n}{2}$, you can prove it by induction on $n$. – 2012-09-20
2 Answers
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:
$\binom{n}{2}=\frac{n!}{2!\times(n-2)!}=\frac{1}{2}n(n-1)$
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.
-
0nice, I wish I could upvote again :) – 2012-09-20
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$
-
0Yes, I think this is how I once learned it. Thank you. – 2012-09-20