Editing Three utilities problem (section)

{{good article}}
{{short description|Mathematical puzzle of avoiding crossings}}
{{redirect|Water, gas and electricity|the utilities|Public utility|the novel Sewer, Gas & Electric|Matt Ruff}}
[[File:3 utilities problem plane.svg|thumb|Diagram of the three utilities problem on a plane. All lines are connected, but two of them are crossing.]]
{{multiple image
|image1=Graph K3-3.svg
|image2=Complex polygon 2-4-3-bipartite graph.png
|total_width=360
|footer=Two views of the utility graph, also known as the Thomsen graph or <math>K_{3,3}</math>}}
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 (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 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]] <math>K_{3,3}</math>, with vertices representing the houses and utilities and edges representing their connections, has a [[graph embedding]] in the plane. The impossibility of the puzzle corresponds to the fact that <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 question of minimizing the [[Crossing number (graph theory)|number of crossings]] in drawings of complete bipartite graphs is known as [[Turán's brick factory problem]], and for <math>K_{3,3}</math> the minimum number of crossings is one.

<math>K_{3,3}</math> is a graph with six vertices and nine edges, 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 is a [[well-covered graph]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]], and the smallest non-planar [[Laman graph|minimally rigid graph]].