Les sept ponts de Königsberg
Voici le plan de la ville et le graphe dessiné par Leonhard Euler en 1735 pour résoudre le problème : les quartiers (A, B, C et D) sont les sommets, le "degré" d'un sommet est le nombre d'arêtes (de ponts) qui y arrivent.
Chaque passage par un sommet détruit 2 arêtes. En dehors des points de départ et d'arrivée, chaque sommet doit donc être de degré pair. Tous les sommets sont de degrés impairs, il n'y a pas de solution !