Utility graph
The classical mathematical puzzle known as the three utilities problem; the three cottages problem or sometimes water, gas and electricity 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 electricity companies. 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. It 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; it has also been called the Thomsen graph.
A review of the problem's history is given by Kullman who states that most published references to the problem characterize it as "very ancient". 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". Dudeney also published the same puzzle previously, in The Strand Magazine in 1913.
Another early version of the problem involves connecting three houses to three wells. 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.
...
Wikipedia