Em uma festa, os convidados se cumprimentaram com apertos de mão. Mostre que a quantidade de pessoas que apertaram mãos um número ímpar de vezes é par.

Passo 1

O enunciado pede para mostrar que, em uma festa em que os convidados se cumprimentam com apertos de mão, a quantidade de pessoas que deram um número ímpar de apertos de mão é par. Para isso, vamos usar a teoria de grafos e o Lema das Mãos Dadas, que relaciona o grau dos vértices ao número de arestas.

Passo 2

Modelamos cada pessoa por um vértice v_i de um grafo simples e cada aperto de mão por uma aresta. O número de apertos de mão feitos pela pessoa v_i corresponde ao seu grau \deg(v_i).

Passo 3

Pelo Lema das Mãos Dadas, a soma dos graus de todos os vértices é o dobro do número de arestas:
\sum_{i=1}^{n}\deg(v_i) \;=\; 2\,|E|.
Como 2\,|E| é um número par, segue que \sum_{i=1}^{n}\deg(v_i) é par.

Passo 4

Seja k a quantidade de vértices com grau ímpar. Podemos escrever
\sum_{i=1}^{n}\deg(v_i) =\sum_{\deg(v_i)\,\text{par}}\deg(v_i) +\sum_{\deg(v_i)\,\text{ímpar}}\deg(v_i).í
A soma dos graus pares é um número par e a soma de k inteiros ímpares tem a mesma paridade de k. Como o total da soma é par, a parte correspondente aos graus ímpares também deve ser par, o que só ocorre se k for par.

Resposta

A quantidade de pessoas que apertaram mãos um número ímpar de vezes é par.

Exercícios relacionados