DevLe lemme des poignées de main est la première égalité fondamentale de la théorie des graphes : dans tout graphe, la somme des degrés des sommets est égale à deux fois le nombre d'arêtes.
Énoncé
Soit $G = (V, E)$ un graphe simple non orienté. Alors : $$\sum_{v \in V} \deg(v) = 2 |E|$$
Corollaire immédiat : dans tout graphe, le nombre de sommets de degré impair est pair.
Démonstration
Procédons par double comptage des paires (sommet, arête incidente).
D'une part, en sommant sur les sommets : chaque sommet $v$ est incident à $\deg(v)$ arêtes, donc le total est $\sum_{v} \deg(v)$.
D'autre part, en sommant sur les arêtes : chaque arête a deux extrémités, donc est comptée 2 fois. Total : $2|E|$.
Les deux comptages sont égaux. ∎
L'analogie sociale
L'appellation « poignées de main » vient de l'analogie : si des personnes se serrent la main, la somme du nombre de poignées données par chacun est égale à deux fois le nombre total de poignées — car chaque poignée implique deux personnes.
Conséquence pratique : dans une réunion, le nombre de participants ayant donné un nombre impair de poignées est toujours pair.
À retenir
Ce lemme illustre une technique majeure en combinatoire : le double comptage. Compter le même ensemble de deux façons différentes donne une égalité non triviale.
Corollaire et applications
Le corollaire le plus célèbre : dans tout graphe, le nombre de sommets de degré impair est pair.
Démonstration : la somme des degrés vaut $2|E|$, qui est pair. Si $k$ sommets avaient un degré impair, la somme des degrés aurait la même parité que $k$. Donc $k$ est pair.
Application : dans toute réunion, le nombre de personnes ayant serré un nombre impair de mains est pair. Amusant à vérifier empiriquement !
Extension aux graphes orientés
Pour un graphe orienté, on définit le degré entrant $d^-(v)$ et le degré sortant $d^+(v)$. Chaque arête orientée contribue exactement 1 à un degré entrant et 1 à un degré sortant. Donc :
$$\sum_{v \in V} d^-(v) = \sum_{v \in V} d^+(v) = |E|$$
Deux égalités au lieu d'une, mais pas le facteur 2 : chaque arête n'a qu'une origine et qu'une destination, pas deux extrémités symétriques.
Une question ou une suggestion ? Écrivez-nous.