Sept sommets de degré trois

1. Non. Le lemme des poignées de main donne ${\sum }_{s}d(s)=2m$, donc la somme des degrés est paire. Ici elle vaudrait $7\times 3=21$, qui est impair. Aucun graphe ne convient — et l'argument ne dépend ni de la connexité, ni de la présence de boucles.

2. Oui. La somme vaut $8\times 3=24$, donc $m=12$ : la condition nécessaire est levée. Un exemple : le cube $Q_3$, dont les sommets sont les huit mots de trois bits et les arêtes relient deux mots différant d'un bit. Chaque sommet a bien trois voisins, et $m=12$. Vérifié par programme : degrés tous égaux à $3$, $12$ arêtes, et le graphe est biparti — les mots de poids pair d'un côté, ceux de poids impair de l'autre.

Noter la dissymétrie : la parité de la somme est une condition nécessaire, jamais suffisante. La suite $(3,3,1,1)$ a une somme paire, $8$, et aucun graphe ne la réalise — vérifié par énumération exhaustive de tous les graphes à quatre sommets. Le troisième problème ci-après donne le critère complet.

3. Le nombre de sommets de degré impair est pair. Séparons la somme des degrés selon leur parité :

$$\underset{\text{pair}}{\underbrace{\sum _{d(s)\text{pair}}d(s)}}+\sum _{d(s)\text{impair}}d(s)=2m\text{(pair)}.$$

La seconde somme est donc paire. Or c'est une somme de nombres impairs : elle n'est paire que si le nombre de termes l'est. Vérifié sur des graphes tirés au hasard : $n=7$, $m=6$, degrés $(1,3,1,3,2,2,0)$ — quatre sommets impairs.

Ce que ce résultat sert. C'est le premier de toute une famille d'arguments de parité en théorie des graphes ; le plus célèbre en découle directement : un graphe connexe admet un parcours eulérien — passant une fois par chaque arête — si et seulement s'il a zéro ou deux sommets de degré impair. Un seul est impossible, par le résultat ci-dessus.