Three utilities problem: Difference between revisions

Revision as of 07:26, 24 October 2021

Revision as of 07:33, 24 October 2021

Line 15:

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

==Puzzle solutions==

Line 57:

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

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

Mathematically, the problem can be formulated in terms of [[graph drawing]]s of the [[complete bipartite graph]] <math>K_{3,3}</math>. This graph

makes an early appearance in {{harvtxt|Henneberg|1908}}.{{r|henneberg}} 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.

The three utilities problem is the question of whether this graph is a [[planar graph]].{{r|bona}}

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

==References==