Démonstration : Lemme des poignées de mains

Le lemme des poignées de mains

Dans un graphe simple, fini et non orienté $G=(V,E)$ , la somme des degrés des sommets est égale à deux fois le nombre d’arêtes :

$\sum_{v\in V}d(v)=2|E|.$

La fonction $d$ associe à chaque sommet $v\in V$ son degré, c’est-à-dire le nombre d’arêtes incidentes à $v$ .

Chaque arête possède exactement deux extrémités. En additionnant les degrés de tous les sommets, chaque arête est donc comptée exactement deux fois.

Considérons l’ensemble des incidences

$I=\{(v,e)\in V\times E\mid v\in e\}.$

En regroupant les incidences par sommet, un sommet $v$ apparaît dans exactement $d(v)$ paires. Ainsi,

$|I|=\sum_{v\in V}d(v).$

En les regroupant par arête, chaque arête $e$ possède exactement deux extrémités. Ainsi,

$|I|=\sum_{e\in E}2=2|E|.$

Les deux expressions comptent le même ensemble $I$ , donc $\sum_{v\in V}d(v)=2|E|$ .