São marcados 15 pontos no plano. É possível ligar esses pontos de tal forma que, ao final do processo, cada ponto esteja ligado a exatamente 5 outros pontos?

Passo 1

O enunciado pede um grafo simples com n=15 vértices (os pontos) em que cada vértice tenha grau 5 (isto é, esteja ligado a exatamente 5 outros vértices). O conteúdo aqui é Teoria dos Grafos, mais especificamente o Lema das Mãos Dadas (handshake lemma), que diz que a soma dos graus dos vértices em qualquer grafo simples é sempre um número par.

Passo 2

Pelo Lema das Mãos Dadas, sejam d_1, d_2,\dots,d_{15} os graus dos 15 vértices. Temos
\sum_{i=1}^{15}d_i = 2E,
onde E é o número de arestas. Se quisermos d_i=5 para todo i, então
\sum_{i=1}^{15}d_i = 15 \times 5 = 75.
Porém 75 é ímpar, o que contradiz o fato de que \sum d_i deve ser par.

Resposta

Não é possível.

Exercícios relacionados