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
vértices (os pontos) em que cada vértice tenha grau
(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
os graus dos 15 vértices. Temos
onde
é o número de arestas. Se quisermos
para todo
, então
Porém
é ímpar, o que contradiz o fato de que
deve ser par.
Resposta
Não é possível.