Three utilities problem: Difference between revisions

Revision as of 06:56, 24 October 2021

Revision as of 07:14, 24 October 2021

Line 5:

|image1=Graph K3-3.svg

|image2=Complex polygon 2-4-3-bipartite graph.png

|total_width=480400

|image3=K33 one crossing.svg

|footer=ThreeTwo views of the utility graph, also known as the Thomsen graph or <math>K_{3,3}</math>}}

|total_width=480

|footer=Three 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 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?}}

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}} This graph 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]].

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>. TheVersions puzzleof has been generalized in [[Turán's brick factorythe problem]], askingon fornonplanar thesurfaces minimumsuch number of crossings in drawings of other complete bipartite graphs. <math>K_{3,3}</math> isas a [[toroidal graphtorus]], meaning that a version of the utilities problem drawn on aor [[coffeeMöbius mugstrip]] instead of a flat surface can be solved. <math>K_{3,3}</math> is also a [[well-covered graph]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]], and the smallest non-planar [[Laman graph|minimally rigid graph]].

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

==History==

Line 27 ⟶ 28:

As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in 19th-century publications both in early studies of [[structural rigidity]]{{r|dixon}} 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|coxeter}}

==Puzzle solutions==

==Impossibility==

===Unsolvability===

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

Line 36 ⟶ 38:

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>, violating this inequality, so the utility graph cannot be planar.{{r|kappraff}}{{Clear|left}}

===Changing the rules===

==Generalizations==

{{multiple image|total_width=480

|image1=3_utilities_problem_plane3_utilities_problem_torus.svg|caption1=OnSolution on a plane or sphere, one crossing is neededtorus

|image2=3_utilities_problem_torus3 utilities problem moebius.svg|caption2=Solution to the three utilities problem on a torusMö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 cottages and companies are drawn on a [[coffee mug]] or other such surface instead of a flat plane can be solved.{{r|parker}} Similarly, if the puzzle is presented on a sheet of paper, it may be solved after twisting and gluing the paper to form a [[Möbius strip]].{{r|larsen}}

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

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}} Similarly, if the puzzle is presented on a sheet of paper, it may be solved after twisting and gluing the paper 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 the cottages or utilities.{{r|dud17}}

==Properties of the utility graph==

[[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|ps09}}{{Clear|left}}

===Rigidity===

ItThe isutility alsograph <math>K_{3,3}</math> is a [[Laman graph]], meaning that for [[almost all]] placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a [[Rigid transformation|rigid motion]] of the whole plane, and that none of its spanning subgraphs have the same [[rigid system|rigidity]] property. It is the smallest example of a nonplanar Laman graph.{{r|streinu}} Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.{{r|dixon|wh07}} For general-position embeddings, a [[polynomial equation]] describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.{{r|wh07}}

===Other graph-theoretic properties===

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

The utility graph <math>K_{3,3}</math> is the [[Cage (graph theory)|(3,4)-cage]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]].{{r|coxeter}} 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 equal. <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}}

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

The utility graph <math>K_{3,3}</math> is the [[Cage (graph theory)|(3,4)-cage]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]].{{r|coxeter}} 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 equal. <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}}

It is also a [[Laman graph]], meaning that for [[almost all]] placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a [[Rigid transformation|rigid motion]] of the whole plane, and that none of its spanning subgraphs have the same [[rigid system|rigidity]] property. It is the smallest example of a nonplanar Laman graph.{{r|streinu}} Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.{{r|dixon|wh07}} For general-position embeddings, a [[polynomial equation]] describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.{{r|wh07}}

===Generalizations===

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

[[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|ps09}}{{Clear|left}}

{{clear}}

==References==

{{reflist|refs=