Un graphe où tous les sommets ont le même degré est dit régulier.
Objectif
Compter les arêtes de deux graphes réguliers, et découvrir que le second ne peut pas exister.
Rappels
La somme des degrés de tous les sommets vaut deux fois le nombre d'arêtes. C'est le lemme des poignées de main, et il se démontre en comptant les extrémités d'arêtes de deux façons.
Pièges
La troisième question ne demande pas un nombre d'arêtes réel, mais ce que la formule rendrait. Le résultat n'étant pas entier, aucun graphe ne répond à la description : c'est une preuve d'impossibilité, obtenue sans dessiner quoi que ce soit.
Un degré n'est pas un nombre de voisins distincts quand le graphe admet des boucles ou des arêtes multiples. Ici le graphe est simple, et les deux coïncident.