Three utilities problem: Difference between revisions

Revision as of 22:01, 30 November 2021

Revision as of 22:09, 30 November 2021

Line 7:

|total_width=360

|footer=Two views of the utility graph, also known as the Thomsen graph or <math>K_{3,3}</math>}}

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 (geometry)|plane]]. When posing it in the early 20th century, [[Henry Dudeney]] wrote that it was already an old problem. It is an [[List of impossible puzzles|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.

This puzzle can be formalized as a problem in [[topological graph theory]] by asking whether the [[complete bipartite graph]] <math>K_{3,3}</math>, haswith avertices [[graphrepresenting drawing]]the houses and utilities and edges representing their connections, has a [[graph embedding]] in the [[Plane (geometry)|plane]]. InThe this form, it is an [[Listimpossibility of impossible puzzles|impossiblethe puzzle]]: it is not possiblecorresponds to connectthe allfact nine lines without crossing, becausethat <math>K_{3,3}</math> is not a [[planar graph]]. Multiple proofs of this impossibility are known, and form part of the proof of [[Kuratowski's theorem]] characterizing planar graphs by two forbidden subgraphs, one of which {{nowrap|is <math>K_{3,3}</math>.}} The Versionsquestion of minimizing the problem[[Crossing onnumber nonplanar(graph surfacestheory)|number suchof as a [[toruscrossings]] orin [[Möbiusdrawings strip]],of orcomplete thatbipartite allowgraphs connectionsis toknown passas through[[Turán's otherbrick housesfactory orproblem]], utilitiesand for <math>K_{3,3}</math> canthe beminimum solvednumber of crossings is one.

<math>K_{3,3}</math> is often referred to as the '''utility graph''' in reference to the problem;{{r|gs93}} it has also been called the '''Thomsen graph''' after 19th-century chemist [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]]. It has six vertices, split into two subsets of three vertices, and nine edges, one for each of the nine ways of pairing a vertex from one subset with a vertex from the other subset. It is a [[well-covered graph]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]], and the smallest non-planar [[Laman graph|minimally rigid graph]]. Although it is nonplanar, it can be drawn with a single crossing, a fact that has been generalized in [[Turán's brick factory problem]], asking for the minimum number of crossings in drawings of other complete bipartite graphs.