Lema do aperto de mão

Na teoria do grafos, um ramo da matemática, o lema do aperto de mão é a afirmação que todo grafo não-direcionado finito tem um número par de vértices de grau ímpar (o número de arestas ligadas ao vértice). Em termos coloquiais, num grupo de pessoas das quais algumas apertam mãos, um número par de pessoas deve ter apertado um número ímpar de mãos de outras pessoas.

Nesse grafo, um número par de vértices (os quatro vértices enumerados 2, 4, 5, e 6) tem grau ímpar. A soma dos graus dos vértices é 2 + 3 + 2 + 3 + 3 + 1 = 14, o dobro do número de arestas.

O lema do aperto de mãos é uma consequência da fórmula da soma dos graus (também chamado às vezes de lema do aperto de mão),

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

para um grafo com conjunto de vértices V e conjunto de arestas E. Ambos os resultados foram provados por Leonhard Euler (1736) no seu artigo famoso sobre o problema das Sete pontes de Königsberg que iniciou o estudo da teoria dos grafos.

Os vértices de grau ímpar em um grafo são às vezes chamados de nós ímpares ou vértices ímpares; nessa terminologia, o lema do aperto de mão pode ser reescrito como a afirmação que todo grafo possui um número par de nós ímpares.

Prova

A prova de Euler para a fórmula da soma dos graus usa a técnica de contagem dupla: ele conta o número de pares incidentes (v,e) onde e é uma aresta e vértice v é um dos seus pontos terminais, de duas maneiras diferentes. Vértice v pertence a deg(v) pares, onde deg(v) (o grau de v) é o número de arestas incidentes a ele. Então o número de pares incidentes é a soma dos graus. No entanto, cada aresta no grafo pertence a exatamente dois pares incidentes, um para cada um dos seus pontos terminais; então, o número de pares incidentes é 2|E|. Já que essas duas fórmulas contam o mesmo conjunto de objetos, elas devem ter valores iguais.

Numa soma de inteiros, a paridade da soma não é afetada por termos pares na soma; a soma total é par quando há um número par de termos ímpares, e ímpar quando há um número ímpar de termos ímpares. Já que um lado da fórmula da soma dos graus é o número par 2|E|, então a soma no outro lado deve ter um número par de termos ímpares; ou seja, deve haver um número par de vértices de grau ímpar.

De modo alternativo, é possível utilizar uma indução matemática para provar que o número de vértices de grau ímpar é par, removendo uma aresta por vez de um dado grafo e utilizando uma análise de caso nos graus dos seus pontos terminais para determinar o efeito da sua remoção na paridade do número de vértices de grau ímpar.

Grafos regulares

A fórmula de soma de graus implica que todo grafo r-regular com n vértices tem nr/2 arestas. Em particular, se r é impar então o número de arestas é divisível por r.

Grafos infinitos

Um grafo infinito que não obedece o lema do aperto de mão

O lema do aperto de mão não se aplica a grafos infinitos, mesmo quando eles possuem apenas um número finito de vértices de grau ímpar. Por exemplo, um grafo de caminho infinito com um ponto terminal possui apenas um vértice de grau ímpar ao invés de ter um número par de tais vértices.

Grafos de troca

Várias estruturas combinatoriais listadas por Cameron & Edmonds (1999) podem ser demonstradas pares em número através de uma relação com o número de vértices ímpares em um "grafo de troca" apropriado.

Por exemplo, como  C. A. B. Smith provou, em qualquer grafo cúbico G deve haver um número par de ciclos Hamiltonianos através de qualquer aresta fixa uv; Thomason (1978) usou uma prova baseada no lema do aperto de mão para expandir esse resultado aos grafos G nos quais todos os vértices possuem grau ímpar. Thomason define um grafo de troca H onde os vértices estão em uma correspondência um-por-um com os caminhos Hamiltonianos começando em u e continuando por v. Dois tais caminhos p₁ e p₂ estão conectados por uma aresta em H se for possível obter p₂ adicionando uma nova aresta ao fim de p₁ e removendo outra aresta do meio de p₁; isso é uma relação simétrica, então H é um grafo não-direcionado. Se um caminho p termina em um vértice w, então o vértice correspondente a p em H tem grau igual ao número de maneiras em que p pode ser estendido por uma aresta que não se conecta de volta a u; ou seja, o grau desse vértice em H  ou é deg(w) − 1 (um número par) se p não forma parte de um ciclo Hamiltoniano com uv, ou deg(w) − 2 (um número ímpar) se p é parte de um ciclo Hamiltoniano com uv. Já que H possui um número par de vértices ímpares, G deve ter um número parde ciclos Hamiltonianos com uv.

Complexidade computacional

Em conexão com o método de grafo de troca para provar a existência de estruturas combinatoriais, é interessante perguntar com qual eficiência essas estruturas podem ser encontradas. Por exemplo, suponha que é dado como entrada um ciclo Hamiltoniano em um grafo cúbico; pelo teorema de Smith existe um segundo ciclo. Quão rápido esse segundo ciclo pode ser encontrado? Papadimitriou (1994) investigou a complexidade computational de questões como essas, ou de modo mais geral de encontrar um segundo vértice de grau ímpar em um grande grafo definido implicitamente. Ele definiu a classe de complexidade PPA para encapsular problemas como esse; uma classe fortemente relacionada definida sobre grafos direcionados, PPAD, atraiu atenção significativa em teoria dos jogo algorítmica porque calcular um Equilíbrio de Nash é computacionalmente equivalente ao problema mais difícil dessa classe.

Outras aplicações

O lema do aperto de mão também é usado em provas do lema de Sperner e do caso  of the piecewise linear case of the mountain climbing problem.

Referências

• Cameron, Kathie; Edmonds, Jack (1999), «Some graphic uses of an even number of odd nodes», Annales de l'Institut Fourier, 49 (3): 815–827, MR 1703426, doi:10.5802/aif.1694 .
• Euler, L. (1736), «Solutio problematis ad geometriam situs pertinentis» (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140 . Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press .
• Papadimitriou, Christos H. (1994), «On the complexity of the parity argument and other inefficient proofs of existence», Journal of Computer and System Sciences, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7 .
• Thomason, A. G. (1978), «Hamiltonian cycles and uniquely edge colourable graphs», Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, pp. 259–268, MR 499124, doi:10.1016/S0167-5060(08)70511-9 .