Sept ponts, une seule promenade ?

Le fil du corrigé reprend exactement celui du sujet : nous partons de dessins, nous mettons en place le langage minimal des graphes, puis nous transformons deux observations de comptage en une preuve d'impossibilité pour les sept ponts de Königsberg.

I — Deux dessins, un même graphe

(a) Dans les deux dessins, les voisinages sont les mêmes :

• A est voisin de B et C ;
• B est voisin de A, C et D ;
• C est voisin de A, B et E ;
• D est voisin de B et E ;
• E est voisin de C et D.

Les longueurs, les angles et la position des sommets changent, mais pas les connexions. Les deux dessins représentent donc le même graphe.

(b) Le graphe possède 5 sommets et 6 arêtes. Les voisins de B sont A, C et D. Les voisins de E sont C et D.

(c) Les degrés sont : A : 2 ; B : 3 ; C : 3 ; D : 2 ; E : 2. Ils sont identiques sur les deux dessins, ce qui confirme que le degré dépend des connexions et non de la géométrie du tracé.

IDÉEUn croisement de traits sans sommet marqué ne crée aucune nouvelle connexion. Cette convention permet de dessiner librement un même graphe de nombreuses façons.

II — Compter deux fois

(a) Le dessin comporte 8 arêtes, donc 8 poignées de main. Les degrés valent A : 3 ; B : 3 ; C : 3 ; D : 2 ; E : 3 ; F : 2. Leur somme vaut

$$3+3+3+2+3+2=16=2\times8.$$

(b) Lorsqu'on additionne les degrés, chaque arête est comptée une fois à chacune de ses deux extrémités. Elle est donc comptée exactement deux fois. Pour tout graphe fini,

$$\boxed{\text{somme des degrés}=2\times\text{nombre d'arêtes}}.$$

(c) Le membre de droite est deux fois un entier : la somme de tous les degrés est donc paire. La somme des degrés pairs est elle aussi paire ; la somme des degrés impairs doit donc être paire.

Or la somme d'un nombre impair de nombres impairs est impaire : en ajoutant des nombres impairs un par un, la parité alterne, et après un nombre impair d'additions on obtient une somme impaire. Pour que la somme des degrés impairs soit paire, il faut donc qu'il y ait un nombre pair de sommets de degré impair.

IDÉECette conclusion ne dépend d'aucun dessin particulier : elle vient uniquement du fait qu'une arête possède deux extrémités.

III — Traverser chaque arête une seule fois

(a) Pour G1, tous les sommets ont degré 2. Par exemple,

$$A\to B\to C\to D\to A$$

utilise chaque arête exactement une fois et revient au point de départ : c'est un circuit eulérien.

Pour G2, les degrés sont : A : 3 ; B : 2 ; C : 3 ; D : 2. Un exemple de chaîne eulérienne est

$$A\to B\to C\to D\to A\to C.$$

Elle part de A et finit en C, précisément les deux sommets de degré impair.

Pour G3, le centre O est de degré 3 et chacune des trois feuilles A, B et C est de degré 1. Les quatre sommets sont donc de degré impair. Aucun parcours utilisant chaque arête exactement une fois ne peut satisfaire la règle démontrée ensuite.

(b) Les exemples suggèrent la règle suivante : un circuit eulérien ne laisse aucun sommet de degré impair ; une chaîne eulérienne qui ne revient pas au départ semble avoir exactement deux sommets de degré impair, son départ et son arrivée.

(c) Prenons un sommet qui n'est ni le départ ni l'arrivée. Chaque fois que le parcours y arrive par une arête, il doit en repartir par une autre. Les arêtes utilisées à ce sommet se regroupent donc par paires : son degré est pair.

Si le parcours revient à son point de départ, le même appariement vaut aussi au sommet de départ : tous les degrés sont pairs.

Si le départ et l'arrivée sont distincts, le départ possède une arête de départ qui n'est pas appariée avec une arrivée antérieure, et l'arrivée possède une arête d'arrivée qui n'est pas appariée avec un départ ultérieur. Tous les autres passages se font par paires. Ainsi seuls le départ et l'arrivée peuvent avoir un degré impair.

Cette démonstration établit exactement l'obstacle dont nous avons besoin : si un graphe possède plus de deux sommets de degré impair, aucune chaîne eulérienne n'est possible.

IV — Retour à Königsberg

(a) On peut choisir les lettres comme suit : A pour la rive nord, B pour l'île centrale de Kneiphof, C pour la zone orientale de Lomse et D pour la rive sud. Avec ce choix, les sept ponts donnent : deux arêtes entre A et B, deux arêtes entre B et D, une arête entre B et C, une entre A et C et une entre C et D.

Il s'agit bien d'un seul graphe à quatre sommets ; le fait que plusieurs ponts relient parfois les mêmes zones se traduit simplement par plusieurs arêtes entre les mêmes sommets.

(b) Non. Le raisonnement de la question 3(c) ne change pas : chaque pont reste une arête distincte, et chaque passage intermédiaire associe toujours une arête d'arrivée à une arête de départ.

(c) Les degrés valent alors :

• A : 3 ;
• B : 5 ;
• C : 3 ;
• D : 3.

Les quatre sommets ont donc un degré impair. On vérifie aussi que la somme des degrés vaut $3+5+3+3=14=2\times7$, comme elle le doit pour sept arêtes.

(d) Un circuit eulérien exigerait que tous les sommets aient un degré pair : c'est impossible ici. Une chaîne eulérienne ouverte pourrait avoir au plus deux sommets de degré impair, son départ et son arrivée : ici il y en a quatre. Quel que soit le lieu où l'on commence et celui où l'on souhaite terminer, il est donc impossible de traverser chacun des sept ponts exactement une fois.

(e) Le graphe a oublié les distances, les angles, la forme du fleuve, la disposition des rues et des bâtiments, ainsi que la longueur des ponts. Il a conservé ce qui est décisif pour le problème : quelles zones sont reliées par quels ponts, en comptant séparément les ponts multiples.

Quelques essais infructueux ne concernent que les parcours effectivement testés. Ils ne disent rien des très nombreux ordres de traversée qui n'ont pas été essayés. Le raisonnement sur les degrés, lui, s'applique à toute chaîne eulérienne possible ; il élimine donc d'un seul coup tous les choix de départ, d'arrivée et d'ordre des ponts.

Un mot d'histoire

Euler présente son travail à l'Académie de Saint-Pétersbourg en 1735 ; l'article latin Solutio problematis ad geometriam situs pertinentis paraît en 1741. Le texte historique ne parle pas encore de « graphes » au sens moderne : Euler code les parcours par les régions successivement visitées et raisonne sur le nombre de passages. Notre représentation par sommets et arêtes est donc une reformulation moderne du geste d'abstraction, pas la notation littérale d'Euler.

Illustration disponible dans le corrigé PDF.

Figure 1 du texte d'Euler : redessin vectoriel de la figure historique ; l'original est accessible dans les sources ci-dessous.

Euler avait correctement dégagé l'obstacle de parité et formulé le bon critère général. En revanche, la partie qui affirme que ces conditions suffisent n'est pas démontrée avec la rigueur moderne dans son article. L'étude historique de Sachs, Stiebitz et Wilson attribue la première preuve publiée complète de cette suffisance à Carl Hierholzer en 1873. C'est précisément la question laissée ouverte dans le « Pour prolonger » du sujet : lorsque les degrés ne bloquent plus le parcours, comment en construire un ?

Sources

[SOURCE] Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, E53, Commentarii academiae scientiarum Petropolitanae, vol. 8, publication 1741. Euler Archive — notice et texte.

[SOURCE] H. Sachs, M. Stiebitz et R. J. Wilson, « An historical note: Euler's Königsberg letters », Journal of Graph Theory 12(1), 1988, 133–139. DOI.

[SOURCE] Carl Hierholzer, « Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren », Mathematische Annalen 6, 1873, 30–32. EuDML.

[SOURCE] Teo Paoletti, « Leonard Euler's Solution to the Königsberg Bridge Problem », MAA Convergence. Article.

[SOURCE] Carte historique utilisée dans le sujet : Bogdan Giuşcă, Konigsberg bridges.png, d'après une carte du domaine public, licence CC BY-SA 3.0 / GFDL. Wikimedia Commons.

[SOURCE] Schéma simplifié des sept ponts : diagramme de la configuration de Königsberg, licence CC BY-SA 3.0 / GFDL. Wikimedia Commons — 7 bridges.svg.

[SOURCE] Figure 1 d'Euler : copie nettoyée du dessin historique, domaine public. Wikimedia Commons.