Three utilities problem: Difference between revisions

Revision as of 04:19, 28 April 2024

Latest revision as of 20:16, 25 June 2025

(4 intermediate revisions by 2 users not shown)

Line 2:

{{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 showing lines inon a plane. CanAll eachlines house beare connected, tobut eachtwo utility,of withthem no connection linesare crossing?.]]

{{multiple image

|image1=Graph K3-3.svg

Line 8:

|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''', oralso sometimesknown 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 inon thea [[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.

Line 23:

The three utilities problem can be stated as follows:

{{quotation|Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections on a two-dimensional plane 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. Its mathematical formalization is part of the field of [[topological graph theory]] which studies the [[embedding]] of [[Graph (discrete mathematics)|graph]]s on [[surface (topology)|surface]]s. An important part of the puzzle, but one that is often not stated explicitly in informal wordings of the puzzle, is that the houses, companies, and lines must all be placed on a two-dimensional surface with the topology of a [[Plane (geometry)|plane]], and that the lines are not allowed to pass through other buildings; sometimes this is enforced by showing a drawing of the houses and companies, and asking for the connections to be drawn as lines on the same drawing.{{r|intuitive|bona}}

Line 264:

| title = Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference Held at the University of Adelaide August 27–29, 1975

| volume = 560

| isbn = 978-3-540-08053-4

| year = 1976}}</ref>

Line 296 ⟶ 297:

| year = 2009}}</ref>

<ref name=quarrelsome>{{citation|title=Mathematical Puzzles of Sam Loyd|first=Sam|last=Loyd|author-link=Sam Loyd|editor-first=Martin|editor-last=Gardner|editor-link=Martin Gardner|publisher=Dover Books|year=1959|isbn=((9780486204987))<!-- isbn ok, for later printing of same edition by same publisher -->|contribution=82: The Quarrelsome Neighbors|page=79|contribution-url=https://books.google.com/books?id=QCy6DzgqcI4C&pg=PA79}}</ref>

<ref name=streinu>{{citation