Three utilities problem

The classical <a href="/facts/Mathematical_puzzle/3WtWnGVC">mathematical puzzle</a> 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 <a href="/facts/Plane_(geometry)/tAUtRFcn">plane</a>. When posing it in the early 20th century, <a href="/facts/Henry_Dudeney/YSSBQgoK">Henry Dudeney</a> wrote that it was already an old problem. It is an <a href="/facts/List_of_impossible_puzzles/pEDabEN9">impossible puzzle</a>: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a <a href="/facts/Torus/J9SkaV1W">torus</a> or <a href="/facts/M%C3%B6bius_strip/35kzqqFL">Möbius strip</a>, or that allow connections to pass through other houses or utilities, can be solved.
This puzzle can be formalized as a problem in <a href="/facts/Topological_graph_theory/TAQ2DdVB">topological graph theory</a> by asking whether the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> 
 
 
 
 
 K
 
 3
 ,
 3
 
 
 
 
 {\displaystyle K_{3,3}}
 
, with vertices representing the houses and utilities and edges representing their connections, has a <a href="/facts/Graph_embedding/IyBA3ttM">graph embedding</a> in the plane. The impossibility of the puzzle corresponds to the fact that 
 
 
 
 
 K
 
 3
 ,
 3
 
 
 
 
 {\displaystyle K_{3,3}}
 
 is not a <a href="/facts/Planar_graph/plREagr9">planar graph</a>. Multiple proofs of this impossibility are known, and form part of the proof of <a href="/facts/Kuratowski%27s_theorem/Enph2grQ">Kuratowski's theorem</a> characterizing planar graphs by two forbidden subgraphs, one of which is 
 
 
 
 
 K
 
 3
 ,
 3
 
 
 
 
 {\displaystyle K_{3,3}}
 
. The question of minimizing the <a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">number of crossings</a> in drawings of complete bipartite graphs is known as <a href="/facts/Tur%C3%A1n%27s_brick_factory_problem/o2770HsJ">Turán's brick factory problem</a>, and for 
 
 
 
 
 K
 
 3
 ,
 3
 
 
 
 
 {\displaystyle K_{3,3}}
 
 the minimum number of crossings is one.

 
 
 
 
 K
 
 3
 ,
 3
 
 
 
 
 {\displaystyle K_{3,3}}
 
 is a graph with six vertices and nine edges, often referred to as the utility graph in reference to the problem. It has also been called the Thomsen graph after 19th-century chemist <a href="/facts/Hans_Peter_J%C3%B8rgen_Julius_Thomsen/QINr2v4E">Julius Thomsen</a>. It is a <a href="/facts/Well-covered_graph/zudc7Bro">well-covered graph</a>, the smallest <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free</a> <a href="/facts/Cubic_graph/6M32WUIJ">cubic graph</a>, and the smallest non-planar <a href="/facts/Laman_graph/vdg4s2zR">minimally rigid graph</a>.

Three utilities problem open-in-new

Three utilities problem