Le musée - Résolution

Il s'agit de chercher un circuit passant une fois et une seule par toutes les pièces (circuit Hamiltonien).
Chercher un tel circuit avec 46 pièces et un bon paquet de couloirs est une tâche éprouvante, surtout qu'il s'agit ici de prouver qu'il n'y en a pas !
Il existe plusieurs critères nécessaires à l'existence de circuits Hamiltoniens.
Nous allons utiliser ici la formule de Grinberg.
Cette formule s'applique aux graphes planaires. Soit un graphe planaire Hamiltonien.
Un circuit Hamiltonien sépare alors (planaire !) le plan en deux régions, l'intérieur du circuit et l'extèrieur. Les arcs diagonaux (ceux du graphe qui ne font pas partie du circuit) définissent des régions intérieures et des régions extérieures. Soient F_k le nombre de régions intérieures possédant k frontières, et G_k le nombre de régions extèrieures possédant k frontières. La formule de Grinberg affirme alors que :

 ∑(k - 2)(F_k - G_k) = 0    c'est à dire (F₃ - G₃) + 2(F₄ - G₄) + 3(F₅ - G₅) + ... = 0

Il n'y a pas de régions à 1 frontière (boucle) et 2 frontières (2 arcs entre deux sommets donnés) quand le graphe est est un graphe simple. Sinon les boucles et les arcs en doubles peuvent être éliminés car ne servent pas dans la recherche d'un circuit Hamiltonien : ils ramènent à un sommet déja visité.

Dans l'exemple ci dessus, F₄=1, F₅=1, F₆=1, G₃=2, G₅=1 et G₆=1 (l'extèrieur du graphe), tous les autres sont nuls et on a bien 1(0-2)+2(1-0)+3(1-1)+4(1-1)=0.

Appliquons cette formule au graphe du musée. Il n'y a que des régions à 5, 8 et 9 frontières. S'il existe un circuit Hamiltonien sur ce graphe, il sépare les régions en régions intérieures F_i et régions extèrieures G_i au circuit et on a :
3(F₅ - G₅) + 6(F₈ - G₈) + 7(F₉ - G₉) = 0
Bien sûr on ne connaît pas grand chose des F_i et G_i tant qu'on ne connaît pas le circuit Hamiltonien, à part F₉ = 0 et G₉ = 1, car la seule région à 9 frontières est l'extèrieur du graphe.
Donc 3(F₅ - G₅) + 6(F₈ - G₈) = 7 ou encore 3X + 6Y = 7
Cette équation est impossible car 7 n'est pas un multiple de 3.
Il n'y a donc pas de circuit Hamiltonien dans le graphe et le gardien chef a menti.