Three utilities problem: Difference between revisions

Revision as of 23:08, 24 October 2021

Latest revision as of 20:16, 25 June 2025

(31 intermediate revisions by 12 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_blank.svg|thumb|The three utilities problem. Can each house be connected to each utility, with no connection lines crossing?]]

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

Line 7 ⟶ 8:

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

The classical [[mathematical puzzle]] known as the '''three utilities problem'''; the '''three cottages problem''' or sometimes '''water, gas and electricity''' can be stated as follows:

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.

{{quotation|Suppose three cottages each need to be connected to the water, gas, and electricity companies, with a separate line from each cottage to each company. Is there a way to make all nine connections without any of the lines crossing each other?}}

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

The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation. It is part of the [[mathematical]] 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 cottages, 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 cottages and companies, and asking for the connections to be drawn as lines on the same drawing. In more formal [[graph theory|graph-theoretic]] terms, the problem asks whether the [[complete bipartite graph]] <math>K_{3,3}</math> is [[planar graph|planar]].{{r|intuitive|bona}}

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

The three utilities problem can be stated as follows:

{{quotation|Suppose three cottageshouses each need to be connected to the water, gas, and electricity companies, with a separate line from each cottagehouse to each company. Is there a way to make all nine connections 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. ItIts mathematical formalization is part of the [[mathematical]] 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 cottageshouses, 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 cottageshouses and companies, and asking for the connections to be drawn as lines on the same drawing. In more formal [[graph theory|graph-theoretic]] terms, the problem asks whether the [[complete bipartite graph]] <math>K_{3,3}</math> is [[planar graph|planar]].{{r|intuitive|bona}}

The answer to the puzzle is negative: it is not possible to connect all nine lines without crossing, or in mathematical terms the graph <math>K_{3,3}</math> connecting each cottage to each utility is not planar. 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 is <math>K_{3,3}</math>. Versions of the problem on nonplanar surfaces such as a [[torus]] or [[Möbius strip]] can be solved.

<math>K_{3,3}</math>In ismore oftenformal referred to as the '''utility[[graph theory|graph'''-theoretic]] in reference toterms, the problem;{{r|gs93}} itasks haswhether alsothe been[[complete called the '''Thomsenbipartite graph''']] after<math>K_{3,3}</math> 19th-centuryis chemista [[Hans Peterplanar Jørgen Julius Thomsen|Julius Thomsengraph]]. ItThis graph has six vertices, split intoin two subsets of three: one vertex for verticeseach house, and one for each utility. It has nine edges, one edge for each of the nine wayspairings of pairing a vertex from one subsethouse with a vertexutility, fromor themore otherabstractly subset.one Itedge isfor aeach [[well-coveredpair graph]],of thea smallestvertex [[triangle-freein graph|triangle-free]]one [[cubic graph]],subset and thea smallestvertex non-planarin [[Lamanthe graph|minimallyother rigid graph]]subset. AlthoughPlanar itgraphs isare nonplanar,the itgraphs that can be drawn withwithout acrossings singlein crossingthe plane, aand factif thatsuch hasa beendrawing generalizedcould inbe [[Turán'sfound, brickit factorywould problem]], asking forsolve the minimumthree numberutilities of crossings in drawings of other complete bipartite graphspuzzle. {{r|intuitive|bona}}

==Puzzle solutions==

Line 21 ⟶ 33:

[[File:3_utilities_problem_proof.svg|thumb|[[Proof without words]]: One house is temporarily deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions. Whichever region the deleted house is placed into, the similarly shaded utility is outside the region. By the [[Jordan curve theorem]], a line connecting them must intersect one of the existing lines.]]

As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other.

In other words, the graph <math>K_{3,3}</math> is not planar. [[Kazimierz Kuratowski]] stated in 1930 that <math>K_{3,3}</math> is nonplanar,{{r|kuratowski}} from which it follows that the problem has no solution. {{harvtxt|Kullman|1979}}, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ <math>K_{3,3}</math> ] is non-planar".{{r|kullman1979}}

One proof of the impossibility of finding a planar embedding of <math>K_{3,3}</math> uses a case analysis involving the [[Jordan curve theorem]].{{r|ayres}} In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.{{r|trudeau}}

Alternatively, it is possible to show that any [[bridgeless graph|bridgeless]] [[bipartite graph|bipartite]] planar graph with <math>V</math> vertices and <math>E</math> edges has <math>E\le 2V-4</math> by combining the [[Euler characteristic|Euler formula]] <math>V-E+F=2</math> (where <math>F</math> is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (the vertices around each face must alternate between houses and utilities, so each face has at least four edges, and each edge belongs to exactly two faces). In the utility graph, <math>E=9</math> and <math>2V-4=8</math>, violatingso in the utility graph it is untrue that <math>E\le 2V-4</math>. Because it does not satisfy this inequality, so the utility graph cannot be planar.{{r|kappraff}}{{Clear|left}}

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

K_3,3 is a [[toroidal graph]], which means it can be embedded without crossings on a [[torus]], a surface of genus one,{{r|harary}} and that versions of the puzzle in which the cottages and companies are drawn on a [[coffee mug]] or other such surface instead of a flat plane can be solved.{{r|parker}} A version of the puzzle with four houses and four utilities on the torus can also be solved.{{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}}

}}

K<submath>K_{3,3}</submath> is a [[toroidal graph]], which means that it can be embedded without crossings on a [[torus]], a surface of genus one,.{{r|harary}} andThese thatembeddings solve versions of the puzzle in which the cottageshouses and companies are drawn on a [[coffee mug]] or other such surface instead of a flat plane can be solved.{{r|parker}} AThere is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities on the torus can also be solved.{{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}}

Another way of changing the rules of the puzzle that would make it solvable, suggested by [[Henry Dudeney]], is to allow utility lines to pass through other cottageshouses or utilities than the ones they connect.{{r|dud17}}

==Properties of the utility graph==

Line 42 ⟶ 56:

===Other graph-theoretic properties===

<math>K_{3,3}</math> is a [[triangle-free graph]], in which every vertex has exactly three neighbors (a [[cubic graph]]). Among all such graphs, it is the smallest. Therefore, it is the [[Cage (graph theory)|(3,4)-cage]], the smallest graph that has 3three neighbors per vertex and in which the shortest cycle has length 4four.{{r|tutte}}

Like all other [[complete bipartite graph]]s, it is a [[well-covered graph]], meaning that every [[maximal independent set]] has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and obviously they are of equal sizes. <math>K_{3,3}</math> is one of only seven [[cubic graph|3-regular]] [[k-vertex-connected graph|3-connected]] well-covered graphs.{{r|cer93}}

===Generalizations===

[[File:K33 one crossing.svg|thumb|upright=0.5|Drawing of <math>K_{3,3}</math> with one crossing]]

Two important characterizations of planar graphs, [[Kuratowski's theorem]] that the planar graphs are exactly the graphs that contain neither <math>K_{3,3}</math> nor the [[complete graph]] <math>K_5</math> as a subdivision, and [[Wagner's theorem]] that the planar graphs are exactly the graphs that contain neither <math>K_{3,3}</math> nor <math>K_5</math> as a [[minor (graph theory)|minor]], make use of and generalize the non-planarity of <math>K_{3,3}</math>.{{r|little}}

[[File:K33 one crossing.svg|thumb|upright=0.5|Drawing of <math>K_{3,3}</math> with one crossing]]

[[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}} Sam 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 134 ⟶ 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 163 ⟶ 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 176 ⟶ 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 184 ⟶ 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 195 ⟶ 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 216 ⟶ 225:

| title = The utilities problem

| volume = 52

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

}}</ref>

<ref name=kuratowski>{{citation

Line 226 ⟶ 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 253 ⟶ 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 285 ⟶ 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 296 ⟶ 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 303 ⟶ 315:

| doi = 10.1002/cber.188601902285

| issue = 2

| journal = Berichte der deutschenDeutschen chemischenChemischen Gesellschaft

| pages = 2944–2950

| title = Die Constitution des Benzols

Line 327 ⟶ 339:

| title = A family of cubical graphs

| volume = 43

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

<ref name=wh07>{{citation

| last1 = Walter | first1 = D.

| last2 = Husty | first2 = M. L.

| editor1-first = Jean-Pierre | editor1-last = Merlet

| editor2-first = Marc | editor2-last = Dahan

| contribution = On a nine-bar linkage, its possible configurations and conditions for paradoxical mobility

| contribution-url = https://geometrie.uibk.ac.at/obsolete/institutsangehoerige/husty/dld/A681.pdf

| publisher = [[International Federation for the Promotion of Mechanism and Machine Science]]

| title = 12th World Congress on Mechanism and Machine Science (IFToMM 2007)

| year = 2007}}</ref>