Three utilities problem: Difference between revisions

Revision as of 22:14, 30 November 2021

Revision as of 22:15, 30 November 2021

Line 18:

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

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 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.{{r|intuitive|bona}}

In more formal [[graph theory|graph-theoretic]] terms, the problem asks whether the [[complete bipartite graph]] <math>K_{3,3}</math> is a [[planar graph]]. This graph has six vertices in two subsets of three: one vertex for each house, and one for each utility. It has nine edges, one edge for each of the pairings of a house with a utility, or more abstractly one edge for each pair of a vertex in one subset and a vertex in the other subset. Planar graphs are the graphs that can be drawn without crossings in the plane, and if such a drawing could be found, it would solve the three utilities puzzle.{{r|intuitive|bona}}