Three utilities problem: Difference between revisions

Revision as of 05:01, 1 December 2021

Latest revision as of 20:16, 25 June 2025

(15 intermediate revisions by 10 users not shown)

Line 1:

{{good article}}

{{short description|Mathematical problempuzzle of avoiding crossings}}

{{redirect|Water, gas and electricity|the utilities|Public utility|the novel Sewer, Gas & Electric|Matt Ruff}}

[[File:3_utilities_problem_blank3 utilities problem plane.svg|thumb|TheDiagram of the three utilities problem. Canon eacha houseplane. beAll connectedlines toare each utilityconnected, withbut notwo connectionof linesthem are 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.

<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]].

==History==

A review of the history of the three utilities problem is given by {{harvtxt|Kullman|1979}}. He states that most published references to the problem characterize it as "very ancient".{{r|kullman1979}} In the earliest publication found by Kullman, {{harvs|first=Henry|last=Dudeney|authorlink=Henry Dudeney|year=1917|txt}} names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than [[electric lighting]], or even [[town gas|gas]]".{{r|dud17}} Dudeney also published the same puzzle previously, in ''[[The Strand Magazine]]'' in 1913.{{r|dud13}} A competing claim of priority goes to [[Sam Loyd]], who was quoted by his son in a posthumous biography as having published the problem in 1900.{{r|early}}

Another early version of the problem involves connecting three houses to three wells.{{r|3wells}} It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern [[numberlink]] puzzles.{{r|fountains}} Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.{{r|quarrelsome}}

As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in late 19th-century and early 20th-century publications both in early studies of [[structural rigidity]]{{r|dixon|henneberg}} and in [[chemical graph theory]], where [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]] proposed it in 1886 for the then-uncertain structure of [[benzene]].{{r|thomsen}} In honor of Thomsen's work, <math>K_{3,3}</math> is sometimes called the Thomsen graph.{{r|bollobas}}

==Statement==

Line 35 ⟶ 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 57 ⟶ 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}}

==History==

A review of the history of the three utilities problem is given by {{harvtxt|Kullman|1979}}. He states that most published references to the problem characterize it as "very ancient".{{r|kullman1979}} In the earliest publication found by Kullman, {{harvs|first=Henry|last=Dudeney|authorlink=Henry Dudeney|year=1917|txt}} names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than [[electric lighting]], or even [[town gas|gas]]".{{r|dud17}} Dudeney also published the same puzzle previously, in ''[[The Strand Magazine]]'' in 1913.{{r|dud13}} A competing claim of priority goes to [[Sam Loyd]], who was quoted by his son in a posthumous biography as having published the problem in 1900.{{r|early}}

Another early version of the problem involves connecting three houses to three wells.{{r|3wells}} It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern [[numberlink]] puzzles.{{r|fountains}} Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.{{r|quarrelsome}}

As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in late 19th-century and early 20th-century publications both in early studies of [[structural rigidity]]{{r|dixon|henneberg}} and in [[chemical graph theory]], where [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]] proposed it in 1886 for the then-uncertain structure of [[benzene]].{{r|thomsen}} In honor of Thomsen's work, <math>K_{3,3}</math> is sometimes called the Thomsen graph.{{r|bollobas}}

==References==

{{reflist|refs=

<ref name=3wells>{{citation|title=Puzzle|url=https://books.google.com/books?id=yLSTwH0pINIC&q=%22three+houses+and+three+wells%22&dq=%22three+houses+and+three+wells%22&hl=en&sa=X&ved=0ahUKEwiS-aHrteXNAhVD9mMKHYXNBWo4FBDoAQg2MAY|magazine=Successful Farming|year=1914|volume=13|page=50}}; {{citation|url=https://books.google.com/books?id=w8tPAQAAMAAJ&pg=PA392|year=1916|magazine=The Youth's Companion|page=392|volume=90|issue=2|title=A well and house puzzle}}.</ref>

<ref name=ayres>{{citation

Line 140 ⟶ 141:

| publisher = Thomas Nelson

| title = Amusements in mathematics

| year = 1917| volume = 100 | issue = 2512 | doi = 10.1038/100302a0 | bibcode = 1917Natur.100..302. | s2cid = 10245524 }}. The solution given on [https://archive.org/details/amusementsinmath00dude/page/200 pp. 200–201] involves passing a line through one of the other houses.</ref>

<ref name=early>{{citation

Line 169 ⟶ 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

| year = 1993| isbn = 978-1-4419-2835-1 | s2cid = 206657798 }}. See p. 437: "<math>K_{3,3}</math> is known as the ''utility graph''".</ref>

<ref name=harary>{{citation

Line 182 ⟶ 183:

| title = Recent results in topological graph theory

| volume = 15

| year = 1964}};| seeissue p.= 4093–4 | hdl = 2027.<42/ref>41775 | s2cid = 123170864 | hdl-access = free

}}; see p. 409.</ref>

<ref name=henneberg>{{citation

Line 190 ⟶ 192:

| pages = 345–434

| title = Encyklopädie der Mathematischen Wissenschaften

| volume = 4.1

| year = 1908| issue = 1
}}. See in particular [https://archive.org/stream/encyklomath104encyrich/#page/n425 p.&nbsp;403].</ref>

<ref name=intuitive>{{citation

Line 201 ⟶ 204:

| title = Some historical and intuitive aspects of graph theory

| volume = 2

| year = 1960| issue = 2 | bibcode = 1960SIAMR...2..123H }}</ref>

<ref name=kappraff>{{citation

Line 222 ⟶ 225:

| title = The utilities problem

| volume = 52

| year = 1979}}<| doi = 10.1080/ref>0025570X.1979.11976807

}}</ref>

<ref name=kuratowski>{{citation

Line 232 ⟶ 236:

| url = http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf

| volume = 15

| year = 1930}}</ref>

| doi = 10.4064/fm-15-1-271-283|doi-access=free }}</ref>

<ref name=larsen>{{citation

Line 259 ⟶ 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 291 ⟶ 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

| last = Streinu | first = Ileana | author-link = Ileana Streinu

| doi = 10.1007/s00454-005-1184-0 | doi-access=free

| issue = 4

| journal = [[Discrete & Computational Geometry]]

Line 302 ⟶ 308:

| title = Pseudo-triangulations, rigidity and motion planning<!-- Note: Journal website has incorrect title in metadata; do not change title to "Acute triangulations of polygons" -->

| volume = 34

| year = 2005| s2cid = 25281202 }}. See p. 600: "Not all generically minimally rigid graphs have embeddings as pseudo-triangulations, because not all are planar graphs. The smallest example {{nowrap|is <math>K_{3,3}</math>".}}</ref>

<ref name=thomsen>{{citation

Line 309 ⟶ 315:

| doi = 10.1002/cber.188601902285

| issue = 2

| journal = Berichte der deutschenDeutschen chemischenChemischen Gesellschaft

| pages = 2944–2950

| title = Die Constitution des Benzols

Line 333 ⟶ 339:

| title = A family of cubical graphs

| volume = 43

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

<ref name=wh07>{{citation