3 utility problem

Jump to navigation Jump to search “Water, gas and electricity” redirects here. For the utilities, see 3 utility problem utility.

Did not find what they wanted? Try here

Can each house be connected to each utility, with no connection lines crossing? Without using a third dimension or sending any of the connections through another company or cottage, is there a way to make all nine connections without any of the lines crossing each other? The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation. He states that most published references to the problem characterize it as “very ancient”. Another early version of the problem involves connecting three houses to three wells.

Mathematically, the problem can be formulated in terms of graph drawings of the complete bipartite graph K3,3. In other words, the graph K3,3 is not planar. One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem. In this solution, 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. K3,3 drawn with only one crossing.

Solution to the three utilities problem on a torus. K3,3 is a toroidal graph, which means it can be embedded without crossings on a torus. The utility graph K3,3 is a circulant graph. It is the smallest example of a nonplanar Laman graph, as the other minimal nonplanar graph, K5, is not minimally rigid. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp.