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 A e B de 13 times cada, é possível que cada time faça exatamente 11 jogos contra adversários da própria associação e 3 jogos contra adversários da associação oposta. Vamos modelar isso por um grafo simples G: 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 G=(V,E) com
V = A ;dotcup; B, |A|=|B|=13,
e desejamos que cada vértice de A tenha grau total 14, sendo 11 arestas ligadas a vértices de A e 3 ligadas a vértices de B.

Passo 3

Contagem das arestas entre A e B. Cada vértice de A tem 3 arestas para B, então o total de “aresta cruzadas” é
sumvin AdB(v) ;=; 13 times 3 ;=; 39
Como cada aresta entre A e B é contada uma vez vindo de A e uma vez vindo de B, isso implica também que cada vértice de B teria grau 3 em relação a A, e o número de arestas cruzadas é consistente.

Passo 4

Contagem das arestas dentro de A. Cada vértice de A tem 11 arestas internas, logo a soma dos graus internos em A é
sumvin AdA(v) ;=; 13 times 11 ;=; 143
Pelo Lema das Mãos, essa soma deve ser igual a 2|E(A)|, isto é, um número par, pois 2|E(A)| é sempre par. Mas 143 é ímpar, então não existe uma forma de distribuir 143 “meios-graus” em pares. Logo, essa configuração é impossível.

Resposta

Não é possível cada time jogar 11 vezes dentro da própria associação e 3 vezes contra a outra, pois a contagem de arestas internas em cada associação violaria o Lema das Mãos.

Exercícios de Livros Relacionados