problème des trois maisons

COMBINATOIRE

Enigme posée par Henry Dudeney en 1917 dans Amusements in mathematics.
Un énoncé est : « Un lotissement de trois maisons doit être équipé d’eau, de gaz et d’électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire ? ». Ce problème n’a pas de solution si on reste en dimension 2.
Comme le problème des ponts de Koenigsberg ou de la coloration des cartes, et malgré sa formulation simple, il s’agit d’un problème de topologie. Sa modélisation est un des premiers exemples de graphe planaire .