Pourquoi la somme des degrés d’un graphe vaut-elle deux fois son nombre d’arêtes ?

Réponse courte

Dans un graphe non orienté, chaque arête touche deux sommets et ajoute une unité au degré de chacun. En comptant toutes les incidences, chaque arête est donc comptée deux fois : la somme des degrés vaut 2 fois le nombre d’arêtes.

Comprendre

Compter les extrémités

Le degré d’un sommet est le nombre d’arêtes qui y arrivent. Une arête non orientée possède exactement deux extrémités. Quand on additionne les degrés de tous les sommets, on compte donc chaque extrémité une fois, soit deux contributions par arête. Si le graphe a m arêtes, la somme des degrés est 2m.

Un exemple vérifié

Prenons les arêtes AB, BC, CD, DA et AC. Les degrés de A, B, C et D sont respectivement 3, 2, 3 et 2. Leur somme vaut 3 + 2 + 3 + 2 = 10 ; le graphe a cinq arêtes, et 2 × 5 = 10.

Ce que la formule permet

On peut retrouver le nombre d’arêtes en divisant la somme des degrés par 2. Elle implique aussi qu’un graphe non orienté possède un nombre pair de sommets de degré impair : une somme d’entiers égale à 2m est paire, et une somme est paire seulement si le nombre de ses termes impairs est pair.

Exemples

  • Avec AB, BC, CD, DA et AC, les degrés sont 3, 2, 3, 2 : leur somme vaut 10 = 2 × 5 arêtes.
  • Si trois sommets ont degré 1 et un sommet degré 3, la somme vaut 6 : le graphe possède 6 ÷ 2 = 3 arêtes.

Pièges fréquents

  • Compter chaque arête une seule fois dans la somme des degrés : ses deux extrémités contribuent chacune au degré d’un sommet.
  • Appliquer la formule à un graphe orienté sans préciser les degrés : il faut alors distinguer degrés entrants et sortants, dont les sommes valent chacune le nombre d’arcs.

Et maintenant ?

Questions proches

← Toutes les questions-réponses