Water, gas, and electricity

Water, gas, and electricity

The classical mathematical puzzle known as water, gas, and electricity, the (three) utilities problem, or sometimes the three cottage problem, can be stated as follows:

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


:: K_{3,3}

n=6, m=9

There is no correct solution; it is impossible to connect the three cottages with the three different utilities without at least one of the connections crossing another.

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. This graph is often referred to as the utility graph in reference to the problem. [ [http://mathworld.wolfram.com/UtilityGraph.html Utility Graph] from "mathworld.wolfram.com"] The graph is equivalent to the circulant graph Ci6(1,3). Kazimierz Kuratowski proved in 1930 that K3,3 is nonplanar, and thus that the problem has no solution. The solution can be adduced as a consequence of the Jordan curve theorem. The complete statement on the planarity of graphs (the Kuratowski reduction theorem) encompasses this result.

But K3,3 is toroidal, which means it can be embedded on the torus. In terms of the three cottage problem this means the problem can be solved by punching two holes through the plane (or the sphere) and attaching them with a tube. This changes the topological properties of the surface and using the tube we can connect the three cottages without crossing lines. An equivalent statement is that the graph genus of the utility graph is one, and therefore it cannot be embedded in a surface of genus less than one. A surface of genus one is equivalent to a torus.

One cannot redraw graphs with non-zero genus in the plane without edge intersections.


External links

* [http://mathworld.wolfram.com/UtilityGraph.html Utility Graph] at MathWorld
* [http://www.cut-the-knot.org/do_you_know/3Utilities.shtml 3 Utilities Puzzle] at cut-the-knot
* [http://www.jimloy.com/puzz/puzzle2.htm Proof That the Impossible Puzzle is Impossible]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Office of Gas and Electricity Markets — (Welsh: Swyddfa’r Marchnadoedd Nwy a Thrydan) Non ministerial government department overview Preceding agencies Office of Electricity Regulation Office of Gas Supply Jurisdiction United Kingdom …   Wikipedia

  • Water supply and sanitation in Rwanda — Source: Poverty Reduction Strategy Paper 2002, p. 51 and p. 25, quoting the 2001 inventory of rural water supply systemsDespite favorable rainfall, little use is made of rainwater harvesting, except by a few health centers and churches.Concerning …   Wikipedia

  • Water supply and sanitation in Bolivia — Bolivia’s water and sanitation coverage has greatly improved since 1990 due to a considerable increase in sectoral investment. However, the country continues to suffer from what happens to be the continent’s lowest coverage levels as well as from …   Wikipedia

  • Water supply and sanitation in Germany — Source: Metropolitan Consulting Group: VEWA Vergleich europaeischer Wasser und Abwasserpreise, 2006, p. 7 of the executive summary [http://www.bgw.de/files/pdf/0.1 resource 2006 7 14.pdf] Concerning sanitation, unequalized tariffs are by far the… …   Wikipedia

  • Pacific Gas and Electric Company — For the 1970s rock music band, see Pacific Gas Electric (band). : PG E redirects here. For the Portland, Oregon electric utility, see Portland General Electric. Infobox Company company name = Pacific Gas and Electric Company company company type …   Wikipedia

  • Memphis Light, Gas and Water — The Memphis Light, Gas and Water Division (MLGW) is the largest three service municipal utility in the U.S. with more than 420,000 customers. Since 1939, MLGW has provided electricity, natural gas and water service for Memphis, Tennessee and… …   Wikipedia

  • Water heating — is a thermodynamic process using an energy source to heat water above its initial temperature. Typical domestic uses of hot water are for cooking, cleaning, bathing, and space heating. In industry, both hot water and water heated to steam have… …   Wikipedia

  • Water supply — is the process of self provision or provision by third parties of water of various qualities to different users. Irrigation is covered separately. Global access to waterIn 2004 about 3.5 billion people worldwide (54% of the global population) had …   Wikipedia

  • Gas lighting — For other uses, see Gaslight (disambiguation). Gas lighting is production of artificial light from combustion of a gaseous fuel, including hydrogen, methane, carbon monoxide, propane, butane, acetylene, ethylene, or natural gas. Before… …   Wikipedia

  • Electricity sector in Mexico — Mexico: Electricity sector Data Electricity coverage (2005) 96%(total),(LAC average in 2005: 94.6%) Installed capacity (2006) 58 GW Share of fossil energy 75.3 % …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”