Encyclopedia > Three cottage problem

  Article Content

Three cottage problem

The three cottage problem is a problem in mathematical graph theory:

Suppose there are three cottages that each need 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?

In more formal terms, this asks whether the 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
North Lindenhurst, New York

... size is 3.44. In the town the population is spread out with 25.6% under the age of 18, 7.5% from 18 to 24, 33.8% from 25 to 44, 21.3% from 45 to 64, and 11.8% who are 65 ...

This page was created in 34.8 ms