Three utilities problem: Difference between revisions

Revision as of 08:03, 30 November 2021

Revision as of 22:01, 30 November 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''' or sometimes '''water, gas and electricity''' canasks for non-crossing connections to be stateddrawn between three houses and three utility companies. When posing it in the early 20th century, [[Henry Dudeney]] wrote that it was already an asold follows:problem.

ItThis puzzle can be formalized as a problem in [[topological graph theory]] by asking whether the [[complete bipartite graph]] <math>K_{3,3}</math> has a [[graph drawing]] has a [[graph embedding]] in the [[Plane (geometry)|plane]]. In this form, it is an [[List of impossible puzzles|impossible puzzle]]: it is not possible to connect all nine lines without crossing, or in mathematical terms the graphbecause <math>K_{3,3}</math> connecting each house to each utility 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 is <math>K_{3,3}</math>. 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.

{{quotation|Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house 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 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.

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

==Statement==

It is an [[List of impossible puzzles|impossible puzzle]]: it is not possible to connect all nine lines without crossing, or in mathematical terms the graph <math>K_{3,3}</math> connecting each house 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.

The three utilities problem can be stated as follows:

{{quotation|Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house 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 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.

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

==Puzzle solutions==