= Edge count of a complete graph
{title2=$|E(K_n)|=\binom n2=n(n-1)/2$}
For a <finite set> of $n$ <vertices>, a <simple graph> selects some of their unordered pairs as <edges>. There are $n(n-1)$ ordered pairs of distinct <vertices>; each unordered pair is counted twice, giving $\binom n2$ possibilities. Hence every <simple graph> $G$ on those <vertices> satisfies
$$
|E(G)|\leq\binom n2,
$$
with equality exactly when $G$ is a <complete graph>. The <binomial coefficient> also shows why the count grows quadratically with the number of <vertices>.
Back to article page
