Counting cliques

#cliques#graphs#counting

Statement

In the complete graph $K_n$ , how many triangles are there?

Hint

Choose $3$ vertices.

Show solutionHide solution

Triangles. A triangle is a choice of $3$ vertices: $\binom{n}{3}=\frac{n(n-1)(n-2)}{6}$ .

Conclusion. $\binom{n}{3}$ triangles.