Water, Gas, And Electricity Relationship

Water, Gas, And Electricity Relationship

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 sending any of the connections through another company or cottage are disallowed. Is there a way to make all nine connections without any of the lines crossing each other?

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

Solution

            The utility graph, also known as the Thomsen graph or K_3,3

The answer to the strict puzzle posed above is no; It is impossible to connect the three cottages with the three different utilities without at least one of the connections crossing another. More generalised questions may have different answers.

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 K_3,3 is planar. This graph is often referred to as the utility graph in reference to the problem. The graph is equivalent to the circulant graph Ci₆(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 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 formulan - 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₅as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K_3,3 nor K₅ as a minor, encompass this result.

Generalizations

K_3,3 drawn with only one crossing.

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.

Pál Turán's "brick factory problem" asks more generally for a formula for the minimum number of crossings in a drawing of the complete bipartite graph K_a,bin terms of the numbers of vertices a and b on the two sides of the bipartition. The utility graph K_3,3 may be drawn with only one crossing, but not with zero crossings, so its crossing number is one. A toroidal embedding of K_3,3 may be obtained by replacing the crossing by a tube, as described above, in which the two holes where the tube connects to the plane are placed along one of the crossing edges on either side of the crossing.

Other Graph-Theoretic Properties

The utility graph K_3,3is, like all other complete bipartite graphs, a well-covered graph, meaning that every maximal independent set has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and obviously they are equal. K_3,3 is one of only seven 3-regular 3-connected well-covered graphs.

It is also a Laman graph, meaning that it forms a minimally rigid system when it is embedded (with crossings) in the plane. It is the smallest example of a nonplanar Laman graph, as the other minimal nonplanar graph, K₅, is not minimally rigid.