Étape 1
Déterminons tout d'abord le nombre d'arêtes du graphe $G$.
La somme des degrés de l'ensemble des sommets de $G$ s'écrit :
$$\sum \deg(S) = 4 \times 6 + 4 \times 5 = 24 + 20 = 44$$
Étape 2
D'après le résultat fondamental de la théorie des graphes, la somme des degrés de tous les sommets d'un graphe est égale à deux fois son nombre d'arêtes. Ainsi, le nombre d'arêtes $m_G$ du graphe $G$ est :
$$m_G = \frac{44}{2} = 22$$
Étape 3
Déterminons ensuite le nombre d'arêtes d'un graphe complet d'ordre $8$, noté $K_8$.
Dans un graphe complet d'ordre $n$, chaque sommet est relié à chacun des $n-1$ autres sommets. Le nombre total d'arêtes $m_{K_8}$ est donné par :
$$m_{K_8} = \frac{n(n-1)}{2} = \frac{8 \times 7}{2} = 28$$
Étape 4
Calculons enfin le nombre $k$ d'arêtes supprimées.
Le graphe $G$ étant formé en enlevant $k$ arêtes au graphe complet $K_8$, on obtient :
$$k = m_{K_8} - m_G = 28 - 22 = 6$$
Le nombre d'arêtes supprimées est donc égal à $6$.
Méthode clé
Utiliser le fait que la somme des degrés des sommets est égale au double du nombre d'arêtes du graphe, puis employer la formule du nombre d'arêtes d'un graphe complet $K_n$, égale à $\frac{n(n-1)}{2}$.
Piège à éviter
Oublier de diviser la somme des degrés par 2 pour obtenir le nombre d'arêtes de $G$, ou confondre le degré d'un sommet avec le nombre d'arêtes du graphe.
