biology daily - the biology and biochemistry encyclopedia
biology daily articles and research Encyclopedia Dictionary Forums biology research links Weblinks Pictures Articles Blogs Newsletter

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 K3,3 is planar. Kazimierz Kuratowski proved in 1930 that K3,3 is nonplanar, and thus that the three cottage problem has no solution.

But K3,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.



07-14-2008 23:18:10
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy
BiologyDaily.com 2005. Legal info   Privacy