Exercice : Vocabulaire des graphes et parcours

Étape 1

Étape 1 : Calcul du nombre d'arêtes du graphe initial.
Le graphe initial est un graphe complet d'ordre $n = 7$. Dans un graphe complet d'ordre $n$, chaque sommet est relié à tous les $n - 1$ autres sommets. Le nombre total d'arêtes $M$ du graphe initial est donné par :$$M = \frac{7 \times (7 - 1)}{2} = \frac{42}{2} = 21$$

Étape 2

Étape 2 : Calcul du nombre d'arêtes du graphe final.
Soit $m$ le nombre d'arêtes du graphe après le retrait. La somme des degrés de l'ensemble des sommets d'un graphe est toujours égale au double de son nombre d'arêtes :$$\sum \text{degrés} = 2m$$On sait que la somme des degrés vaut $30$, ce qui équivaut à :$$2m = 30 \implies m = 15$$Le graphe final comporte donc $15$ arêtes.

Étape 3

Étape 3 : Déduction du nombre d'arêtes retirées.
Le nombre d'arêtes retirées $k$ correspond à la différence entre le nombre d'arêtes initial et le nombre d'arêtes final :$$k = M - m = 21 - 15 = 6$$