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.

À 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.
Cours associés (1)
MATH-213: Differential geometry I - curves and surfaces
Ce cours est une introduction à la géométrie différentielle classique des courbes et des surfaces, principalement dans le plan et l'espace euclidien.
Publications associées (20)

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...
ASSOC COMPUTING MACHINERY2020

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...
SPRINGER2020
Afficher plus
Personnes associées (2)
Concepts associés (11)
Graphe birégulier
Dans la théorie des graphes, un graphe birégulier est un graphe biparti dans lequel tous les sommets de chacune des deux parties du graphe ont le même degré. Notons et les deux parties d'un graphe birégulier. Si le degré des sommets de est et si le degré des sommets de est , le graphe est dit -birégulier. vignette|Le graphe biparti complet est -birégulier. Tout graphe biparti complet (figure) est -birégulier. vignette|gauche|Le graphe du dodécaèdre rhombique est birégulier. Le graphe du dodécaèdre rhombique (figure) est -birégulier.
Eulerian path
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.
Degré (théorie des graphes)
thumb|Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est et le degré minimal est . En mathématiques, et plus particulièrement en théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois. Le degré d'un sommet est noté . Dans le cas d'un graphe orienté, on parle aussi du degré entrant d'un sommet , c'est-à-dire le nombre d'arcs dirigés vers le sommet , et du degré sortant de ce sommet , c'est-à-dire le nombre d'arcs sortant de .
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.