Somme des degrés : énoncé (Maths expertes)
Somme des degrés
Dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes.
Démonstration : Somme des degrés
Somme des degrés
Chaque arête a deux extrémités. En additionnant les degrés de tous les sommets, on compte chaque arête exactement deux fois, une fois pour chacune de ses extrémités. La somme des degrés vaut donc deux fois le nombre d'arêtes.
Conséquence : la somme des degrés est paire, donc le nombre de sommets de degré impair est pair.
Lecture d'un graphe
On considère le graphe d'ordre $4$, de sommets $1,2,3,4$, dont les arêtes sont $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ et $\{3,4\}$.
| Sommet | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Degré | 2 | 2 | 3 | 1 |
La somme des degrés est $8=2\times 4$ : il y a bien $4$ arêtes. Le graphe est connexe (tout sommet est relié à $3$). Il n'est pas complet : $1$ et $4$ ne sont pas adjacents. La suite $1-3-4$ est une chaîne de longueur $2$ ; la suite $1-2-3-1$ est une chaîne fermée de longueur $3$.