Lemme des poignées de main

Énoncé du problème

Dans un graphe, on appelle degré d(v) d'un sommet v le nombre d'arêtes qui lui sont incidentes.

Démontrer que dans tout graphe à n sommets et m arêtes : Σ d(v_i) = 2m.
En déduire que le nombre de sommets de degré impair est toujours pair.
Application : dans une soirée, 9 personnes se serrent la main. Est-il possible que chaque personne ait serré exactement 5 mains ?

1. Chaque arête {u,v} contribue 1 au degré de u et 1 au degré de v → elle contribue 2 à la somme totale des degrés. Donc Σ d(v_i) = 2m. ✓

2. Σ d(v_i) = 2m est pair. On écrit Σ(pairs) + Σ(impairs) = pair. Σ(pairs) est pair → Σ(impairs) est pair → le nombre de sommets de degré impair est pair. ✓

3. Si chaque personne a serré 5 mains → 9 sommets tous de degré 5 (impair). Le nombre de sommets de degré impair serait 9 (impair) — contradiction avec le résultat précédent. Impossible.

Énoncé du problème

Solution détaillée