Un peu d'histoire

Dans la ville de Königsberg (maintenant appelée Kaliningrad), il y avait à l'époque 7 ponts reliant les îles ainsi que les deux rives de la ville. La configuration était celle indiquée dans la figure 6.1.

Figure: Esquisse de la ville de Königsberg

Les citoyens de Königsberg passaient souvent le week-end en promenade à pied. Plusieurs personnes se demandaient alors s'il était possible de commencer une promenade sur une île ou sur une rive, terminer la promenade sur n'importe quelle autre (ou la même) île ou rive en passant exactement une fois sur chacun des ponts.

On voit immédiatement qu'il est possible de modéliser le problème de Königsberg sous la forme d'un graphe dont les sommets correspondent aux îles et aux rives et dont les arêtes correspondent aux ponts. Le problème peut alors être formulé de la manière suivante :

Dans un graphe $G$, est-il possible de trouver une chaîne $C = s_1, e_1, s_2, e_2, \ldots, s_m, e_m, s_{m+1}$ telle que $\{e_1, e_2, \ldots, e_m\} = E(G)$ et $\vert E(G)\vert = m$ ?

Autrement dit, il faut d'abord trouver une chaîne du graphe qui passe par toutes les arêtes. De plus, la condition $\vert E(G)\vert = m$ nous garantit qu'aucune arête ne figure plusieurs fois dans la chaîne. Si la même arête figure plusieurs fois, mais $\{e_1, e_2, \ldots, e_m\} = E(G)$, cela veut dire que le cardinal de $E(G)$ (i.e., $\vert E(G)\vert$) est strictement inférieur à $m$.