Un graphe régulier, et un compte impossible

Exercice d'entraînement · niveau 2 · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Degrés et formule d'Euler

É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{n r}{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.

Corrigé

Le nombre d'arêtes. La formule d'Euler dit que la somme des degrés vaut le double du nombre d'arêtes : $\sum_{s} de g (s) = 2 m$ . Ici les $n$ sommets ont tous le degré $r$ , donc la somme vaut $n r$ , d'où $n r = 2 m soit m = \frac{n r}{2} .$

Le cas $n = 5$ , $r = 3$ . La formule donnerait $m = \frac{15}{2}$ , qui n'est pas un entier. Or un nombre d'arêtes est un entier : un tel graphe ne peut pas exister. On peut le dire autrement : $5$ sommets seraient tous de degré impair, alors qu'un graphe a toujours un nombre pair de sommets de degré impair (sinon la somme des degrés, qui vaut $2 m$ , serait impaire).

La condition générale. Pour qu'un graphe $r$ -régulier à $n$ sommets existe, il faut d'abord que $n r$ soit pair, c'est-à-dire que $n$ ou $r$ soit pair. Il faut de plus $r \leq n - 1$ , puisqu'un sommet est relié à des sommets distincts de lui-même : il ne peut en avoir plus de $n - 1$ voisins.

Ces deux conditions suffisent d'ailleurs, mais l'énoncé ne demande que la condition nécessaire — et c'est elle qui rend le service : elle élimine un cas sans qu'on ait à chercher un dessin.

Un exemple pour fixer les idées. Le graphe complet $K_{4}$ est $3$ -régulier à $4$ sommets, avec $m = \frac{4 \times 3}{2} = 6$ arêtes : les six paires de sommets. Ici $n = 4$ est pair, la condition est satisfaite.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.