Sete pontes de Königsberg
Origem: Wikipédia, a enciclopédia livre.
Na cidade de Königsberg (Prússia no século XVIII, atual Kaliningrado, Rússia) havia duas grandes ilhas que, juntas, formavam um complexo que continha sete (7) pontes conforme mostra a figura ao lado.
Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes, sem repetir nenhuma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Leonhard Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.
O genial Euler usou um raciocínio muito simples. Transformou os caminhos em retas e suas intersecções em pontos criando possivelmente o primeiro grafo da história. Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvessem no máximo dois pontos de onde saia um número ímpar de caminhos. A razão de tal coisa é: de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para "entrar" e outro para "sair". Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente.