Subject: Re: Doors and Graphs
Date: Thu, 25 Jun 1998 17:29:42 -0400
From: Alex Bogomolny

Dear Tom:

The puzzle does not have a solution. This follows easily from Euler's trick which reduces it to a problem on a graph.

Replace each room and the outer space with a node. Connect two nodes wherever there exists a door between them - one connection per door.

This gives you a graph with 6 nodes four of which are odd. Degrees of nodes are 5, 5, 9, 4, 5, 4.

Euler's theorem states that if the number of odd nodes is greater than 2, it is impossible to traverse all edges of the graph passing each edge only once.

Do read the above page.

Best regards,
Alexander Bogomolny

|Reply| |Up|

Copyright © 1996-2018 Alexander Bogomolny