Des arêtes aux degrés

Les degrés. Le degré d'un sommet est le nombre d'arêtes qui en partent : on compte, pour chaque sommet, dans combien de paires il figure.

• Sommet $1$ : il apparaît dans $\{1,2\}$ et $\{1,3\}$, donc $\mathrm{deg}(1)=2$.
• Sommet $2$ : dans $\{1,2\}$ et $\{2,3\}$, donc $\mathrm{deg}(2)=2$.
• Sommet $3$ : dans $\{1,3\}$, $\{2,3\}$ et $\{3,4\}$, donc $\mathrm{deg}(3)=3$.
• Sommet $4$ : dans $\{3,4\}$ et $\{4,5\}$, donc $\mathrm{deg}(4)=2$.
• Sommet $5$ : dans $\{4,5\}$ seulement, donc $\mathrm{deg}(5)=1$.

La formule d'Euler. Elle affirme que la somme des degrés vaut le double du nombre d'arêtes : $$2+2+3+2+1=10=2\times 5.$$ Il y a bien $m=5$ arêtes dans la liste : la formule est vérifiée.

Pourquoi elle est vraie. Chaque arête a exactement deux extrémités et contribue donc pour $1$ au degré de chacune : elle est comptée deux fois dans la somme des degrés. C'est le même comptage que celui des poignées de main — chaque poignée engage deux mains.

Un contrôle gratuit. Le nombre de sommets de degré impair est toujours pair. Ici seul le sommet $5$ est de degré impair… ce qui ferait un compte impair ! Vérifions : $\mathrm{deg}(3)=3$ est également impair. Il y a donc deux sommets de degré impair, $3$ et $5$ : le contrôle passe.