Exercice : Vocabulaire des graphes et parcours

Étape 1

Un graphe complet d'ordre $n = 7$, noté $K_7$, possède un nombre d'arêtes donné par la formule : $$m_{K_7} = \frac{n(n - 1)}{2} = \frac{7 \times 6}{2} = 21$$

Étape 2

Le graphe $G$ est obtenu en retirant $4$ arêtes au graphe complet $K_7$. Le nombre d'arêtes $m$ du graphe $G$ est donc : $$m = 21 - 4 = 17$$

Étape 3

D'après la propriété fondamentale de la théorie des graphes, la somme des degrés de tous les sommets d'un graphe est égale au double de son nombre d'arêtes. Ainsi, la somme $S$ des degrés des $7$ sommets de $G$ est : $$S = 2 \times m = 2 \times 17 = 34$$

Étape 4

On calcule la somme des degrés des six sommets connus : $$S_{\text{connus}} = 6 + 5 + 5 + 5 + 4 + 4 = 29$$

Étape 5

On en déduit le degré $d$ du septième sommet par soustraction : $$d = S - S_{\text{connus}} = 34 - 29 = 5$$