Three utilities problem: Difference between revisions

Revision as of 07:18, 25 January 2022

Latest revision as of 20:16, 25 June 2025

(9 intermediate revisions by 7 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 41:

===Changing the rules===

{{multiple image|total_width=480

|image1=3_utilities_problem_torus3 utilities problem moebius.svg|caption1=Solution on a torusMöbius strip

|image2=3 utilities problem moebius3_utilities_problem_torus.svg|caption2=Solution on a Möbius strip}}torus

|image3=4_utilities_problem_torus.svg|caption3=A torus allows up to 4 utilities and 4 houses

}}

<math>K_{3,3}</math> is a [[toroidal graph]], which means that it can be embedded without crossings on a [[torus]], a surface of genus one.{{r|harary}} These embeddings solve versions of the puzzle in which the houses and companies are drawn on a [[coffee mug]] or other such surface instead of a flat plane.{{r|parker}} There is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities.{{r|obeirne|early}} Similarly, if the three utilities puzzle is presented on a sheet of a transparent material, it may be solved after twisting and gluing the sheet to form a [[Möbius strip]].{{r|larsen}}

Line 63 ⟶ 65:

[[Pál Turán]]'s "[[Turán's brick factory problem|brick factory problem]]" asks more generally for a formula for the [[crossing number (graph theory)|minimum number of crossings]] in a drawing of the [[complete bipartite graph]] <math>K_{a,b}</math> in terms of the numbers of vertices <math>a</math> and <math>b</math> on the two sides of the bipartition. The utility graph <math>K_{3,3}</math> may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.{{r|early|ps09}}{{Clear|left}}

==References==

Line 170:

| contribution = Chapter 19: A theory of graphs

| doi = 10.1007/978-1-4757-3837-7

| pagepages = 423–460

| publisher = Springer | ___location = New York

| title = A Logical Approach to Discrete Math

Line 183:

| title = Recent results in topological graph theory

| volume = 15

| year = 1964| issue = 3–4 | hdl = 2027.42/41775 | s2cid = 123170864 | hdl-access = free
}}; see p. 409.</ref>

<ref name=henneberg>{{citation

Line 263 ⟶ 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 295 ⟶ 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

Line 337 ⟶ 339:

| title = A family of cubical graphs

| volume = 43

| year = 1947| issue = 4 | bibcode = 1947PCPS...43..459T | s2cid = 123505185 }}</ref>

<ref name=wh07>{{citation