Water, gas, and electricity

related topics
{math, number, function}
{math, energy, light}
{line, north, south}
{water, park, boat}
{specie, animal, plant}
{company, market, business}

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:

This is intended as an abstract mathematical puzzle and imposes constraints that would not be issues in a practical engineering scenario.

Contents

Solution

The answer is no; 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.[1] 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.

One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem, in which one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding. Alternatively, it is possible to show that any bridgeless bipartite planar graph with n vertices and m edges has m ≤ 2n − 4 by combining the Euler formula n - m + f = 2 (where f is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (because each face has at least four edges and each edge belongs to exactly two faces). In the utility graph, m = 9 and 2n − 4 = 8, violating this inequality, so the utility graph cannot be planar.

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor the complete graph K5 as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor K5 as a minor, encompass this result.

Generalizations

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 connecting 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.

Full article ▸

related documents
Harmonic analysis
Euclidean distance
Galois group
Context-sensitive language
Identity function
Disjoint sets
Lazy initialization
Sedenion
Endomorphism ring
Markov process
Essential singularity
Greibach normal form
Recursive language
Direct sum of groups
Co-NP
Ring homomorphism
Chart parser
Derivative of a constant
Sieve of Eratosthenes
Sigmoid function
Equivalence class
Doubling the cube
Center (group theory)
Constant folding
Hilbert's Nullstellensatz
Measurable function
Gabriel Lamé
Rectangle
Sierpiński carpet
Uniform Resource Locator