Lemme des poignées de main

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Dans ce graphe, un nombre pair de sommets (les quatre sommets numérotés 2, 4, 5, et 6) a des degrés impairs. La somme des degrés des sommets vaut 2 + 3 + 2 + 3 + 3 + 1 = 14, deux fois le nombre d'arêtes.

En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes.

Description[modifier | modifier le code]

Le lemme des poignées de main est une conséquence de la formule de la somme des degrés (qu'on qualifie quelques fois de lemme des poignées de main),

\sum_{v\in V} \deg(v) = 2|E|

pour un graphe ayant un ensemble de sommets V[N 1] et un ensemble d'arêtes E[N 2]. Ce résultat a été prouvé par Leonhard Euler dans son célèbre article de 1736 sur le Problème des sept ponts de Königsberg, texte fondateur de l'étude de la théorie des graphes.

Dans un graphe, on appelle parfois les sommets de degré impair des nœuds impairs ou sommets impairs ; sous cette terminologie, le lemme des poignées de main peut être reformulé ainsi : chaque graphe fini possède un nombre pair de nœuds impairs.

Démonstration[modifier | modifier le code]

La démonstration de la formule de la somme des degrés un exemple de preuve par double dénombrement : on compte de deux façons différentes le nombre des extrémités des arêtes :

  • c'est le double du nombre d'arêtes, chaque arête ayant deux extrémités ;
  • c'est aussi la somme des degrés de chaque sommet.

Déduisons-en le lemme des poignées de mains. Supposons que la somme des degrés comporte un nombre impair de sommets de degré impair et un nombre quelconque (éventuellement nul) de sommets de degré pair. Alors cette somme est impaire, ce qui est impossible puisqu'elle est égale au double du nombre des arêtes. La supposition était donc absurde et le graphe contient donc nécessairement un nombre pair de sommets de degré impair.

On peut aussi démontrer le lemme des poignées de main par récurrence.

Graphes infinis[modifier | modifier le code]

Graphe infini dans « une seule direction ». Le lemme des poignées de mains ne s'applique pas.

Le lemme des poignées de main ne s'applique pas aux graphes infinis, même quand ils ont un nombre fini de sommets de degré impair. Par exemple, un graphe chaîne infini à une seule extrémité (figure) comporte exactement un sommet de degré impair (celui du bout), or 1 est un nombre impair.

Cas des graphes réguliers[modifier | modifier le code]

Le graphe de Petersen est un graphe 3-régulier à 15 arêtes. 15 est bien divisible par 3.

La formule sur la somme des degrés implique que tout graphe régulier de degré r à n sommets possède \frac{r n}{2} arêtes[1]. Une conséquence est que si le degré r est impair, alors le nombre d'arêtes est divisible par r.

Notes[modifier | modifier le code]

  1. V pour vertex qui signifie « sommet » en anglais.
  2. E pour edge qui signifie « arête » en anglais.

Références[modifier | modifier le code]

  1. (en) Joan M. Aldous et Robin J. Wilson, Graphs and Applications: an Introductory Approach, Springer-Verlag,‎ 2000 (ISBN 978-1-85233-259-4), « Theorem 2.2 », p. 44