De la complexité des plans de tables. (ou comment la résolution d'un casse tête simple ouvre des horizons mathématiques insoupçonnés).

Soit 2n personnes invitées à un banquets. Chacun connaît exactement 3 personnes (précision: il s'agit de 3 personnes en dehors de soi-même et il s'agit d'une relation symétrique (si A connaît B alors B connaît A.)). On sait qu'il existe un plan de table (circulaire) tel que chaque convive soit assis à coté de 2 personnes qu'il connaît. Alors, il existe un autre plan de table possible, que l'on ne peut obtenir à partir du premier par symétrie ou par rotation.

Ce sera l'occasion d'une introduction à la théorie des graphes, d'un survol de la notion de graphe hamiltonien (ie: qui admettent des circuits passant une et une seule fois par chaque sommet du graphe) avant d'arriver à une solution du problème à proprement parler.