Three utilities problem: Difference between revisions

Revision as of 23:08, 24 October 2021

Revision as of 07:14, 25 October 2021

Line 7:

|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'''; the '''three cottages problem''' or sometimes '''water, gas and electricity''' 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. 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 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 cottagehouse 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> is 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 has six vertices, split into two subsets of three vertices, and nine edges, one for each of the nine ways of pairing a vertex from one subset with a vertex from the other subset. 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]]. Although it is nonplanar, it can be drawn with a single crossing, a fact that has been generalized in [[Turán's brick factory problem]], asking for the minimum number of crossings in drawings of other complete bipartite graphs.

Line 31:

|image1=3_utilities_problem_torus.svg|caption1=Solution on a torus

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

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 cottageshouses 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}}

Another way of changing the rules of the puzzle that would make it solvable, suggested by 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==