Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Lemme des poignées de main
Résumé
vignette|250px|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.
Considérons un graphe non orienté (V, E) où V est l'ensemble de sommets et E est l'ensemble d'arêtes. Le lemme des poignées de main est une conséquence de la formule de la somme des degrés (qu'on qualifie quelquefois de lemme des poignées de main),
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.
La démonstration de la formule de la somme des degrés constitue 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.
Le nombre d'extrémités des arêtes étant pair d'après le premier point, on en déduit que les contributions impaires dans la somme du deuxième point sont en nombre pair, d'où le résultat.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.