Lema do apertón de mans

Na teoría de grafos, unha rama das matemáticas, o lema do apertón de mans é a afirmación de que todo grafo finito non dirixido ten un número par de vértices de grao impar. Máis trivialmente, nunha xuntanza de varias persoas, nas que algunhas delas danse a man, un número par de persoas terá que estreitar a man a outras persoas un número impar de veces.

 Descrición 
Considere un grafo non dirixido (V, E) onde V é o conxunto de vértices  e E é o conxunto de arestas. O lema do apertón de mans é unha consecuencia da fórmula da suma de graos (que ás veces se chama lema do apertón de mans ),



Este resultado foi probado por Leonhard Euler no seu famoso artigo de 1736 sobre o problema das sete pontes de Königsberg, un texto fundacional no estudo da teoría de grafos.

Nun grafo, os vértices de grao impar chámanse ás veces nodos impares ou vértices impares; baixo esta terminoloxía, o lema do apertón de mans pódese reformular como: cada grafo finito ten un número par de nodos impares.

 Demostración 
Demostrar a fórmula da suma de graos é un exemplo de demostración por dupla contaxe: contamos o número de extremos das arestas de dúas formas diferentes :

 isto é o duplo do número de arestas, tendo cada aresta dous extremos;
 tamén é a suma dos graos de cada vértice.

Sendo o número de extremos das arestas par segundo o primeiro punto, deducimos que as contribucións impares na suma do segundo punto son pares, porque ao total par se restamos as pares o resultado de par menos par é un número par.

 Grafos infinitos 
miniatura| Grafo infinito en "unha dirección". O lema do apertón de mans non aplica.
O lema de apertón de mans non aplica nos grafos infinitos, aínda que teñan un número finito de arestas de grao impar. Por exemplo, un grafo de cadea infinita cun só extremo (figura) ten exactamente un vértice de grao impar (o do final), e 1 é un número impar.

 Caso dos grafos regulares 
miniatura| O grafo de Petersen é un grafo 3-regula con 15 arestas. 15 é divisíbel por 3.
A fórmula para a suma de graos implica que calquera grafo regular de grao  con  vértices ten  arestas.. Unha consecuencia é que se o grao  é impar, entón o número de arestas é divisible por .
 Notas 


 Véxase tamén 

 Bibliografía 

 Outros artigos 
 Teoría de grafos.

Categoría:Teoremas
Categoría:Combinatoria
Categoría:Teoría de grafos