Introdução à Teoria dos Grafos - Aula 8 - Soma dos graus dos vértices

Professor Marcos Paulo Ferreira de Araújo
Aula 8 - Soma dos graus dos vértices
Formalizamos a ideia apresentada nas duas aulas anteriores de contagem dupla, colocando-a na forma de um teorema. O teorema diz que em qualquer grafo a soma dos graus de todos os vértices é igual ao dobro do número de arestas. Utilizamos este resultado para resolver o problema abaixo.Em um certo país existem 200 estradas no total, sendo que uma estrada sempre conecta duas cidades distintas. É possível que de cada cidade partam exatamente 3 estradas?