Deux sommets ont toujours le même degré

Les valeurs possibles. Un sommet est relié à certains des $n-1$ autres, sans boucle ni arête double : son degré appartient à $\{0,1,\dots ,n-1\}$, qui compte $n$ valeurs pour $n$ sommets. Compter ne suffit donc pas — il faut resserrer.

Les deux valeurs extrêmes s'excluent. Supposons qu'un sommet $u$ soit de degré $n-1$ : il est alors adjacent à tous les autres, donc aucun sommet n'est de degré $0$. Réciproquement, si un sommet est de degré $0$, il n'est adjacent à personne, donc aucun sommet n'est adjacent à tout le monde. Les degrés $0$ et $n-1$ ne peuvent pas coexister.

Conclusion. Les degrés prennent donc leurs valeurs dans $\{0,\dots ,n-2\}$ ou dans $\{1,\dots ,n-1\}$ : au plus $n-1$ valeurs pour $n$ sommets. Deux sommets reçoivent nécessairement la même.

Le point à retenir. Dans toute assemblée d'au moins deux personnes, deux d'entre elles connaissent le même nombre de participants. Le comptage brut échouait d'une unité : c'est une incompatibilité entre deux cas extrêmes qui a fourni l'unité manquante.