Three utilities problem

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane.

When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem.

It is an impossible puzzle: it is not possible to connect all nine lines without crossing.

Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

The question of minimizing the number of crossings in drawings of complete bipartite graphs is known as Turán's brick factory problem, and for

He states that most published references to the problem characterize it as "very ancient".

[2] In the earliest publication found by Kullman, Henry Dudeney (1917) names it "water, gas, and electricity".

However, Dudeney states that the problem is "as old as the hills...much older than electric lighting, or even gas".

[3] Dudeney also published the same puzzle previously, in The Strand Magazine in 1913.

[4] A competing claim of priority goes to Sam Loyd, who was quoted by his son in a posthumous biography as having published the problem in 1900.

[5] Another early version of the problem involves connecting three houses to three wells.

[6] It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern numberlink puzzles.

appears in late 19th-century and early 20th-century publications both in early studies of structural rigidity[9][10] and in chemical graph theory, where Julius Thomsen proposed it in 1886 for the then-uncertain structure of benzene.

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.

An important part of the puzzle, but one that is often not stated explicitly in informal wordings of the puzzle, is that the houses, companies, and lines must all be placed on a two-dimensional surface with the topology of a plane, and that the lines are not allowed to pass through other buildings; sometimes this is enforced by showing a drawing of the houses and companies, and asking for the connections to be drawn as lines on the same drawing.

[13][14] In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph

[13][14] As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other.

Kullman (1979), however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [

[16] 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.

Alternatively, it is possible to show that any bridgeless bipartite planar graph with

is a toroidal graph, which means that it can be embedded without crossings on a torus, a surface of genus one.

[19] These embeddings solve versions of the puzzle in which the houses and companies are drawn on a coffee mug or other such surface instead of a flat plane.

[20] There is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities.

[22] Another way of changing the rules of the puzzle that would make it solvable, suggested by Henry Dudeney, is to allow utility lines to pass through other houses or utilities than the ones they connect.

is a Laman graph, meaning that for almost all placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a rigid motion of the whole plane, and that none of its spanning subgraphs have the same rigidity property.

[23] Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.

It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.

Therefore, it is the (3,4)-cage, the smallest graph that has three neighbors per vertex and in which the shortest cycle has length four.

In this graph, the only two maximal independent sets are the two sides of the bipartition, and are of equal sizes.

[27] 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