Pourquoi est-il impossible de traverser une seule fois chacun des sept ponts de Königsberg ?

Parce que chaque morceau de terre de Königsberg touchait un nombre impair de ponts, et qu'une promenade qui traverse chaque pont une seule fois tolère au maximum deux endroits de ce genre : le départ et l'arrivée. Leonhard Euler l'a démontré en 1736, et a posé au passage les fondations de la théorie des graphes.

La ville prussienne, aujourd'hui Kaliningrad, en Russie, s'étendait sur les deux rives de la Pregel, autour de deux îles, le tout relié par sept ponts. L'énigme était simple : peut-on faire une promenade qui traverse chaque pont exactement une fois ?

Le génie d'Euler a été de presque tout jeter. Les rues, les distances et la forme des îles ne comptent pas ; seul importe quelle terre est reliée à quelle autre, et par combien de ponts. Réduis chaque morceau de terre à un point et chaque pont à un trait : tu obtiens ce qu'on appelle aujourd'hui un graphe.

Ensuite, il a compté. Chaque fois que tu arrives sur un morceau de terre par un pont, tu dois repartir par un autre : tout endroit que tu traverses a donc besoin d'un nombre pair de ponts. À Königsberg, une terre avait 5 ponts et les trois autres en avaient 3 chacune. Quatre endroits impairs, mais seuls deux peuvent servir de départ et d'arrivée : la promenade est impossible.

Cette idée de points et de traits fait aujourd'hui tourner le calcul d'itinéraires des GPS et les cartes de liens derrière les sites web et les réseaux sociaux.