Three cottage problem

Encyclopedia : T : TH : THR : Three cottage problem

The three cottage problem is a well-known mathematical puzzle. It can be stated like this

Suppose there are three cottages on a plane (or sphere) and each needs to be connected to the gas, water, and electric companies. Is there a way to do so without any of the lines crossing each other?

The problem is part of the mathematical field of topological graph theory which studies the embedding of graphs on surfaces. In more formal graph theoretic terms the problem asks whether the complete bipartite graph K_3,3 is planar. Kazimierz Kuratowski proved in 1930 that K_3,3 is nonplanar, and thus that the three cottage problem has no solution.

But K_3,3 is toroidal, that is it can be embedded on the torus. In terms of the three cottage problem this means the problem can be solved by punching a hole through the plane (or the sphere). This changes the topological properties of the surface and using the hole we can connect the three cottages without crossing lines.

External links

[3 Utilities Puzzle] at cut-the-knot

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.