Teorema de Euler

Ao estudar o problema de Königsberg, Euler apresentou resultados gerais que são aplicáveis a todos os casos. Euler apresentou e demonstrou vários resultados, a saber: (2)
 
1. Numa rede (grafo sem pontos isolados), o número de vértices de valência (ou grau) ímpar é par.
2. Uma figura que não tenha vértices ímpares pode ser descrita de uma só vez, por um ponto móvel deslocando-se num caminho que começa e acaba num mesmo vértice.
3. Uma figura que tenha dois e só dois nós ímpares pode ser descrita de uma só vez por um ponto móvel partindo de um ponto e acabando noutro.
4. Uma figura que tenha mais do que dois nós ímpares não pode ser descrita de uma só vez.
 
(pode ajudar, pensar em "descrita de uma só vez" como "percorrida sem levantar o lápis" ou "percorrida por um caminho passando por todas as arestas e sem repetição de qualquer delas")
Listing acrescentou um resultado (consequência):
(5) Uma figura que tenha no máximo 2n vértices pode ser percorrida completamente por n caminhos distintos e separados.
 
Um destes resultados é conhecido como o
TEOREMA DE EULER:
Um Grafo admite um circuito de Euler quando e só quando é conexo e todos os seus vértices têm valência par.
 
A demonstração do teorema de Euler, bem como a demonstração dos outros resultados, será uma tarefa a discutir.
 
OUTRO TEOREMA:
Em qualquer grafo, a soma dos graus de todos os vértices é igual ao dobro do número das respectivas arestas.

Tarefas 2.1.2
 
(a) Demonstrar pelo menos um dos resultados de Euler (ou de Listing) ou um dos teoremas.
(b) Procurar na internet dados sobre Listing.
 
(c) Discutir o PROBLEMA DA BOLA:
Sabendo que uma bola de futebol é fabricada unindo pentágonos e hexágonos regulares, de tal forma que cada pentágono é cosido a cinco hexágonos e cada hexágono a três pentágonos e a três hexágonos, alternadamente, investigue sobre se é ímpar ou par o número de pentágonos. (6)
(d) Provar que existe um número ímpar de países fazendo fronteira com um número ímpar de países. (3)
(e) Prove que, numa conferência, o número dos que cumprimentam um número ímpar de participantes é par. (3)

voltar ao sumário