Entre 1970 e 1975, a National Football League (NFL), liga de futebol norte-americana, foi dividida em duas associações, com 13 times em cada associação. Cada time participou de 14 jogos em uma temporada. Seria possível para cada time participar de 11 jogos contra times da sua própria associação e 3 jogos contra times da outra associação? Use um modelo de grafo para responder a essa questão (sem desenhar o grafo).
Passo 1
O enunciado pede para decidir se, num campeonato com duas associações
e
de
times cada, é possível que cada time faça exatamente
jogos contra adversários da própria associação e
jogos contra adversários da associação oposta. Vamos modelar isso por um grafo simples
: cada vértice representa um time e cada aresta um jogo entre dois times. O conteúdo principal é aplicar o Lema das Mãos (Handshake Lemma) para verificar a paridade do número de arestas em cada parte.
Passo 2
Definimos
com
e desejamos que cada vértice de
tenha grau total
, sendo
arestas ligadas a vértices de
e
ligadas a vértices de
.
Passo 3
Contagem das arestas entre
e
. Cada vértice de
tem
arestas para
, então o total de “aresta cruzadas” é
Como cada aresta entre
e
é contada uma vez vindo de
e uma vez vindo de
, isso implica também que cada vértice de
teria grau
em relação a
, e o número de arestas cruzadas é consistente.
Passo 4
Contagem das arestas dentro de
. Cada vértice de
tem
arestas internas, logo a soma dos graus internos em
é
Pelo Lema das Mãos, essa soma deve ser igual a
, isto é, um número par, pois
é sempre par. Mas
é ímpar, então não existe uma forma de distribuir
“meios-graus” em pares. Logo, essa configuração é impossível.
Resposta
Não é possível cada time jogar
vezes dentro da própria associação e
vezes contra a outra, pois a contagem de arestas internas em cada associação violaria o Lema das Mãos.