Three utilities problem: Difference between revisions

Revision as of 15:59, 20 December 2021

Latest revision as of 20:16, 25 June 2025

(13 intermediate revisions by 9 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 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.

<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==

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

Line 182 ⟶ 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 234 ⟶ 236:

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

| volume = 15

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

<ref name=larsen>{{citation

Line 261 ⟶ 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 293 ⟶ 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 335 ⟶ 339:

| title = A family of cubical graphs

| volume = 43

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

<ref name=wh07>{{citation