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 graphtheoretic terms, the problem asks whether the complete bipartite graph K_{3,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 Ci_{6}(1,3). Kazimierz Kuratowski proved in 1930 that K_{3,3} is nonplanar, and thus that the problem has no solution.
One proof of the impossibility of finding a planar embedding of K_{3,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 4cycles 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 K_{3,3} nor the complete graph K_{5} as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K_{3,3} nor K_{5} as a minor, encompass this result.
Generalizations
K_{3,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 ▸
