Démonstration : Lemme des poignées de mains
Cet article présente le lemme des poignées de mains ainsi que sa démonstration.
Le lemme des poignées de mains
Dans un graphe $G = (V, E)$, la somme des degrés des sommets est égale à 2 fois le nombre d’arêtes de ce graphe.
$$\sum_{v \in V}d(v) = 2 |E|$$
La fonction $d$ associe $v\in V$ un sommet à son degré (le nombre d’arêtes sortantes et entrantes = le nombre de sommets voisins).
Intuition de la démonstration
Dans un graphe non orienté, une arête est un ensemble à deux éléments (deux sommets).
La somme de tous les degrés des sommets du graphes étant la somme de toutes les arêtes issues de ce sommet (divisée par 2 car 2 sommets pour une arêtes). L’équation est immédiate.
Démonstration formelle
On a $\sum_{V \in V}d(v) = \sum_{v \in v}|\{v \in e \ | \ \forall e \in E \}|$.
Car le degré d’un sommet est bien le nombre total de fois où est présent le sommet dans toutes les arêtes.
Pour l’égalité suivante, on cherche dans les deux cas à dénombrer le nombre fois où les sommets sont présent dans les vecteurs :
- Le membre de gauche, on cherche à savoir le nombre de fois où est présent le sommet dans toutes les arêtes.
- Le membre de droite, on cherche à savoir quels sont les sommets présents pour chaque arête.
Etant donné qu’on parcourt entièrement le graphe les deux fois, nous avons bien affaire à une égalité.
Or, nous avons : $\sum_{v \in V}|\{v \in e \ | \ \forall e \in E \}| = \sum_{e \in E}|\{v \in E \ | \ \forall v \in V \}|$.
Quel que soit $v$, une arêtes est un ensemble de deux sommets (dans un graphe non orienté). Nous avons donc l’égalité suivante :
Ce qui nous donne : $\sum_{e \in E}|\{v \in e \ | \ \forall e \in E \}| = \sum_{e \in E}2$ .
Ainsi, pour finir, nous avons bien $\sum_{e\in E}2 = 2 \ |E|$.
L’égalité est bien retrouvée.