Lema do apertón de mans

Neste grafo, un número par de vértices (os catro vértices numerados 2, 4, 5 e 6) teñen graos impares. A suma dos graos dos vértices é 2 + 3 + 2 + 3 + 3 + 1 = 14, o duplo do número de arestas.

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 ),

$\sum _{v\in V}\mathrm{deg}(v)=2|E|$

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

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

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 $r$ con $n$ vértices ten $\frac{rn}{2}$ arestas. Unha consecuencia é que se o grao $r$ é impar, entón o número de arestas é divisible por $r$.

Véxase tamén

Outros artigos

• Teoría de grafos.

Modelo:Control de autoridades