Étape 1
Soit $n$ l'ordre du graphe ($n \ge 4$) et $m$ son nombre d'arêtes. Le graphe comporte $4$ sommets de degré $5$ et $n - 4$ sommets de degré $3$.
Étape 2
La somme $S$ des degrés de tous les sommets du graphe est donnée par : $$S = 4 \times 5 + (n - 4) \times 3 = 20 + 3n - 12 = 3n + 8$$
Étape 3
D'après la propriété fondamentale reliant les degrés et les arêtes d'un graphe, la somme des degrés est égale à deux fois le nombre d'arêtes ($S = 2m$). On en déduit l'expression du nombre d'arêtes $m$ en fonction de $n$ : $$m = \frac{3n + 8}{2}$$
Étape 4
Un graphe complet d'ordre $n$ possède quant à lui un nombre total d'arêtes égal à : $$N = \frac{n(n - 1)}{2}$$
Étape 5
D'après les données de l'énoncé, il manque $12$ arêtes au graphe pour devenir complet, ce qui se traduit par l'équation $N - m = 12$, c'est-à-dire : $$\frac{n(n - 1)}{2} - \frac{3n + 8}{2} = 12$$
Étape 6
En multipliant chaque membre de l'équation par $2$, on obtient : $$n(n - 1) - (3n + 8) = 24$$ Ce qui équivaut successivement à : $$n^2 - n - 3n - 8 - 24 = 0$$ $$n^2 - 4n - 32 = 0$$
Étape 7
Résolvons cette équation du second degré. Le discriminant est : $$\Delta = (-4)^2 - 4 \times 1 \times (-32) = 16 + 128 = 144$$ Puisque $\Delta > 0$, l'équation admet deux solutions réelles : $$n_1 = \frac{4 - \sqrt{144}}{2} = \frac{4 - 12}{2} = -4$$ $$n_2 = \frac{4 + \sqrt{144}}{2} = \frac{4 + 12}{2} = 8$$
Étape 8
L'ordre d'un graphe étant un entier strictement positif ($n \ge 4$), la solution $n = -4$ est rejetée. L'ordre du graphe est donc $n = 8$.
Méthode clé
Déterminer le nombre d'arêtes $m$ d'un graphe via la somme de ses degrés (qui vaut $2m$) et utiliser la formule $\frac{n(n-1)}{2}$ pour le nombre d'arêtes d'un graphe complet d'ordre $n$.
Piège à éviter
Oublier que le nombre de sommets de degré $3$ est $n-4$ et non $n$, ou confondre l'ordre $n$ (nombre de sommets) avec le nombre d'arêtes.
