Three utilities problem

Common card · No. 411125

The three utilities problem, also known as water, gas and electricity, is a mathematical puzzle that asks for non-crossing connections to be drawn between three houses and three utility companies on a 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 any of them 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. This puzzle can be formalized as a problem in topological graph theory by asking whether the complete bipartite graph K 3 , 3 {\displaystyle K_{3,3}} , with vertices representing the houses and utilities and edges representing their connections, has a graph embedding in the plane. The impossibility of the puzzle...

Read on Wikipedia · Image Cmglee, CC BY-SA 4.0