mathématiques appliquées (ECG 1re année) · Chapitre 3 · Exercice d'entraînement

Un graphe régulier, et un compte impossible

Théorie des graphes · Degrés et formule d'Euler · ★★ niveau 2

Énoncé

Un graphe non orienté sans boucle est dit $r$-régulier lorsque tous ses sommets ont le même degré $r$. Montrer qu'un graphe $r$-régulier à $n$ sommets a $\frac{nr}{2}$ arêtes. En déduire qu'il n'existe pas de graphe $3$-régulier à $5$ sommets, puis donner la condition portant sur $n$ et $r$ pour qu'un tel graphe puisse exister.

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.