Dans la ville prussienne de Königsberg, au XVIIIe siècle, la rivière Pregel traversait le centre-ville ; au milieu de la rivière se trouvaient deux îles, et 7 ponts au total reliaient ces îles entre elles et aux deux rives. Les habitants se posaient depuis longtemps une question : « Peut-on traverser les 7 ponts, chacun exactement une fois, sans en oublier un seul ? » Les promeneurs ont essayé bien des fois, mais personne n'y est jamais arrivé.

En 1736, le mathématicien Leonhard Euler a apporté une réponse définitive à cette question. Mais Euler n'est pas allé traverser les ponts lui-même : il a complètement simplifié le problème. Il a transformé chaque terre (les rives et les îles) en point, et chaque pont en trait reliant ces points. Ainsi dessiné, le problème de Königsberg devient une énigme de « tracé d'un seul trait » : « Peut-on dessiner cette figure sans lever le crayon et sans repasser deux fois sur le même trait ? » Cette idée a été le point de départ de la branche des mathématiques qu'on appelle aujourd'hui la théorie des graphes.

3 5 3 3 Les 4 terres ont un nombre impair de ponts : impossible
Le nombre dans chaque cercle indique combien de ponts touchent cette terre (son degré). 5, 3, 3, 3 : tous impairs

La notion clé ici, c'est le degré. Le nombre de ponts reliés à un point (une terre) s'appelle le degré de ce point. Si tu traverses un point au milieu de ton tracé, tu associes toujours un pont pour arriver à un pont pour repartir. Donc, pour tout point qui n'est ni le départ ni l'arrivée, les ponts s'utilisent deux par deux à chaque passage : le degré de ce point doit toujours être pair.

Un point de degré impair, en revanche, ne peut être que l'une de ces deux choses : le point de départ du trajet (avec un pont de sortie en trop) ou le point d'arrivée (avec un pont d'entrée en trop). Le graphe entier peut donc avoir au plus 2 points de degré impair. S'il n'y en a aucun, tu peux tout tracer d'un seul trait en partant de n'importe où, et même revenir à ton point de départ ; s'il y en a exactement 2, ce n'est possible qu'en partant de l'un et en finissant sur l'autre. Mais s'il y en a 3 ou plus, impossible d'en faire tous des points de départ ou d'arrivée : le tracé d'un seul trait est tout simplement impossible.

Les quatre terres de Königsberg tombaient en plein dans ce piège. Une île était reliée à 5 ponts, et les trois autres terres à 3 ponts chacune : 5, 3, 3, 3. Les quatre terres ont un degré impair. Avec 4 points de degré impair, quel que soit l'ordre essayé par les habitants, traverser les 7 ponts exactement une fois chacun était mathématiquement impossible dès le départ.

À partir de ce seul problème, Euler a créé la théorie des graphes, l'étude des relations faites de points et de traits, et cette idée est aujourd'hui partout dans notre quotidien. La façon dont les applis de cartes trouvent le plus court chemin, dont les réseaux sociaux analysent les amitiés et dont les données circulent sur Internet : tout cela repose sur la théorie des graphes. Une petite curiosité de promeneurs au bord d'une rivière, il y a 300 ans, est à la racine de technologies que nous utilisons tous les jours.

Sur notre page d'activité, tu peux essayer toi-même le tracé d'un seul trait en cliquant sur la vraie carte des ponts de Königsberg, et t'entraîner avec d'autres figures pour voir lesquelles marchent et lesquelles non. À la fin, un tableau des degrés de chaque figure te permet de vérifier qu'il suffit de compter les points de degré impair pour connaître la réponse à l'avance.