Problème des sept ponts de Königsberg

Une telle promenade n'existe pas, et c'est Euler qui donna la solution de ce problème en caractérisant les graphes que l'on appelle aujourd'hui « eulériens » en référence à l'illustre mathématicien, à l'aide d'un théorème dont la démonstration rigoureuse ne fut en fait publiée qu'en 1873, par Carl Hierholzer.

Ce problème n'a sous cette forme non généralisée qu'un intérêt historique, car pour ce cas, il est assez intuitif de démontrer que la promenade demandée n'existe pas. Pour voir cela, il suffit d'associer un graphe à la ville comme dans la figure ci-dessus et de supposer que la promenade recherchée existe. On peut alors, à partir de la promenade, ordonner les sept arêtes du graphe de façon que deux arêtes consécutives par rapport à notre ordre soient adjacentes dans le graphe (en considérant que la dernière et la première arête sont consécutives, puisqu'il y a retour au point de départ).

Ainsi tout sommet du graphe est-il nécessairement incident à un nombre pair d'arêtes (puisque s'il est incident à une arête il est aussi incident à l'arête précédente ou qui lui succède dans l'ordre[2]). Mais le graphe a des sommets qui sont incidents à trois arêtes, d'où l'impossibilité.

Notons que même si l'on renonce à exiger le retour au point de départ, une promenade traversant une et une seule fois chaque pont n'existe pas. Elle existerait si au plus deux sommets du graphe, correspondant aux points à choisir respectivement comme départ et arrivée, étaient incidents à un nombre impair d'arêtes, or les sommets du graphe des ponts de Königsberg sont tous les quatre dans ce cas ; la promenade est donc impossible. Il suffirait cependant de supprimer ou de rajouter un pont quelconque pour que le graphe modifié permette des promenades tous ponts sans retour (seuls deux sommets restant d'incidence impaire). Et ce sont au moins deux ponts, bien choisis, qu'il faudrait ajouter ou retirer pour permettre la promenade avec retour initialement cherché.

Il existe malgré tout des possibilités. Premièrement, d'un point de vue purement géographique, en faisant abstraction de l'esprit dans lequel le problème a été pensé. En effet, en remontant le fleuve jusqu'à sa source, puis en la contournant avant de redescendre jusqu'à ponts de la berge opposée, plusieurs promenades sont possibles. Néanmoins, si l'ensemble des termes de la question sont bien respectés, le fleuve doit vraisemblablement être considéré comme une droite, par nature Infinie, et donc non contournable dans un plan.

Deuxièmement, en considérant que le plan sur lequel les objets du problème reposent, à savoir une droite, des points et des segments, s'inscrit dans un volume à trois dimensions (ou plus), le nombre de possibilités devient infini. En effet, il devient possible de passer d'un côté à l'autre du fleuve en le contournant par-dessus ou par-dessous. Donc dans le monde réel, il s'agirait de le survoler ou à emprunter un tunnel souterrain.

Cependant, on peut se questionner sur le fait que le pont soit conceptuellement un objet en trois dimensions puisque conçu pour enjamber un fleuve, donc d'un point de vue géométrique, à sortir du plan par l'axe Z pour ne pas croiser la droite.

• (la) Leonhard Euler, « Solutio problematis ad geometriam situs pertinentis », dans Mémoires de l'Académie des sciences de Berlin, 1735 (lire en ligne [PDF])
• Édouard Lucas, Récréations mathématiques : Les traversées, les ponts, les labyrinthes les reines, le solitaire, la numération, le baguenaudier, le taquin, vol. I, Paris, Gauthier Villars, 1882 (lire en ligne)
  Le problème des sept ponts fait l'objet de la « récréation n^o 2 » sous le titre « Les ponts de Paris en 1880 ».
  lire en ligne sur Gallica

• Graphe eulérien
• Nœud gordien
• Œuf de Colomb