Ce problème a bien sûr à voir avec la théorie des graphes ; le graphe, dont les arêtes sont les couloirs et les sommets les carrefours, doit être eulérien.

Rappelons nous que :

1. On appelle chaîne eulérienne d’un graphe G une chaîne passant une et une seule fois par chacune des arêtes du graphe, autrement dit une chaîne simple passant par toutes les arêtes du graphe (si une telle chaîne ne passe pas par tous les sommets, les sommets oubliés sont nécessairement de degré 0).
2. On appelle cycle eulérien du graphe G un cycle de G passant par toutes les arêtes du graphe (une unique fois par définition d’un cycle). Un cycle eulérien est donc une chaîne eulérienne fermée simple.
3. On appelle graphe eulérien un graphe pour lequel il existe un cycle eulérien.