Le graphe complet à six sommets

Le degré. Dans un graphe complet, chaque paire de sommets distincts porte une arête. Un sommet donné est donc relié aux $5$ autres : tous les sommets de $K_6$ ont le degré $5$. Plus généralement, dans $K_n$, chaque sommet est de degré $n-1$.

Le nombre d'arêtes. La formule d'Euler donne $$2m=\sum _s\mathrm{deg}(s)=6\times 5=30,\text{donc}m=15.$$

Le cas général. Le même calcul dans $K_n$ donne $2m=n(n-1)$, soit $$m=\frac{n(n-1)}{2}.$$ Pour $n=6$ : $\frac{6\times 5}{2}=15$, ce qui confirme le résultat.

Une seconde lecture. Une arête de $K_n$ est exactement une paire de sommets distincts. On en compte $\frac{n(n-1)}{2}$ : $n$ choix pour la première extrémité, $n-1$ pour la seconde, et chaque paire est ainsi obtenue deux fois, une fois dans chaque ordre — d'où la division par $2$. Oublier cette division est l'erreur la plus fréquente.

Sa matrice d'adjacence a des $0$ sur la diagonale et des $1$ partout ailleurs, ce qui donne bien $6\times 5=30$ coefficients égaux à $1$, soit $15$ arêtes comptées deux fois.