Au XVIIIe siècle, la ville prussienne de Königsberg comptait sept ponts sur sa rivière, et les habitants se demandaient : peut-on faire une promenade qui traverse chaque pont exactement une fois ? Quand le mathématicien Euler a répondu à cette question, une toute nouvelle branche des mathématiques est née : la théorie des graphes.
Réduis chaque terre à un point et chaque pont à un trait : tu obtiens le schéma ci-dessous. Clique sur les points dans l'ordre pour traverser chaque pont exactement une fois — interdit de reprendre un pont. Essaie autant de fois que tu veux et vois si c'est vraiment possible.
Clique sur un point pour commencer, puis sur les points suivants dans l'ordre, et essaie de traverser les sept ponts.
Choisis une figure et essaie de la tracer d'un seul trait. Vois par toi-même quelles figures marchent et lesquelles ne marchent jamais.
Le nombre de traits qui partent d'un point s'appelle son degré. Compte les points de degré impair (sommets impairs) et tu sauras à l'avance si le tracé d'un seul trait est possible.
0 sommet impair → tu peux partir de n'importe où, tout tracer d'un seul trait et revenir à ton point de départ (un cycle eulérien).
2 sommets impairs → ça marche seulement si tu pars de l'un et finis sur l'autre (un chemin eulérien).
3 sommets impairs ou plus → le tracé d'un seul trait n'est jamais possible. Königsberg en avait quatre : voilà exactement pourquoi c'était impossible !
Chaque fois que ton tracé passe par un point, il utilise un trait pour arriver et un trait pour repartir, toujours par paires. Donc, en un point qui n'est ni le départ ni l'arrivée, chaque passage consomme deux traits : son nombre total de traits (son degré) doit être pair.
Seuls deux types de points peuvent avoir un nombre impair de traits : le départ (un trait de plus qui part) et l'arrivée (un trait de plus qui arrive). Il peut donc y avoir au plus deux sommets impairs. Avec trois ou plus, ils ne peuvent pas tous être départ ou arrivée, et le tracé d'un seul trait devient impossible.