Jump to content

Three utilities problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 06:56, 24 October 2021 (It's not quite the projective plane, but I found a thinking-outside-the-box reference for the Möbius strip). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
"Water, gas and electricity" redirects here. For the utilities, see Public utility.
The three utilities problem. Can each house be connected to each utility, with no connection lines crossing?
Three views of the utility graph, also known as the Thomsen graph or

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:

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 graphs on surfaces. 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, 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-theoretic terms, the problem asks whether the complete bipartite graph is planar.[1][2] This graph is often referred to as the utility graph in reference to the problem;[3] it has also been called the Thomsen graph after 19th-century chemist Julius Thomsen.

The answer to the puzzle is negative: it is not possible to connect all nine lines without crossing, or in mathematical terms 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 . The puzzle has been generalized in Turán's brick factory problem, asking for the minimum number of crossings in drawings of other complete bipartite graphs. is a toroidal graph, meaning that a version of the utilities problem drawn on a coffee mug instead of a flat surface can be solved. is also a well-covered graph, the smallest triangle-free cubic graph, and the smallest non-planar minimally rigid graph.

History

A review of the history of the three utilities problem is given by Kullman (1979). He states that most published references to the problem characterize it as "very ancient".[4] In the earliest publication found by Kullman, Henry Dudeney (1917) names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than electric lighting, or even gas".[5] Dudeney also published the same puzzle previously, in The Strand Magazine in 1913.[6]

Another early version of the problem involves connecting three houses to three wells.[7] 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.[8]

Mathematically, the problem can be formulated in terms of graph drawings of the complete bipartite graph . This graph makes an early appearance in Henneberg (1908).[9] 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.[2]

As well as in the three utilities problem, the graph appears in 19th-century publications both in early studies of structural rigidity[10] and in chemical graph theory, where Julius Thomsen proposed it in 1886 for the then-uncertain structure of benzene.[11] In honor of Thomsen's work, is sometimes called the Thomsen graph.[12]

Impossibility

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. In other words, the graph is not planar. Kazimierz Kuratowski stated in 1930 that is nonplanar,[13] from which it follows that the problem has no solution. Kullman, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ ] is non-planar".[4]

One proof of the impossibility of finding a planar embedding of uses a case analysis involving the Jordan curve theorem.[14] In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.[15]

Alternatively, it is possible to show that any bridgeless bipartite planar graph with vertices and edges has by combining the Euler formula (where 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, and , violating this inequality, so the utility graph cannot be planar.[16]

Generalizations

On a plane or sphere, one crossing is needed
Solution to the three utilities problem on a torus

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither nor the complete graph as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither nor as a minor, make use of and generalize the non-planarity of .[17]

K3,3 is a toroidal graph, which means it can be embedded without crossings on a torus, a surface of genus one,[18] 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.[19] 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.[20] Another way of changing the rules of the puzzle that would make it solvable is to allow utility lines to pass through the cottages or utilities.[5]

Pál Turán's "brick factory problem" asks more generally for a formula for the minimum number of crossings in a drawing of the complete bipartite graph in terms of the numbers of vertices and on the two sides of the bipartition. The utility graph may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.[21]

Other graph-theoretic properties

The utility graph is the (3,4)-cage, the smallest triangle-free cubic graph.[12] Like all other complete bipartite graphs, 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. is one of only seven 3-regular 3-connected well-covered graphs.[22]

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 motion of the whole plane, and that none of its spanning subgraphs have the same rigidity property. It is the smallest example of a nonplanar Laman graph.[23] Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.[10][24] 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.[24]

References

  1. ^ Harary, Frank (1960), "Some historical and intuitive aspects of graph theory", SIAM Review, 2: 123–131, doi:10.1137/1002023, MR 0111698
  2. ^ a b Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp. 275–277, ISBN 9789814335232. Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing on a plane surface without crossings".
  3. ^ Gries, David; Schneider, Fred B. (1993), "Chapter 19: A theory of graphs", A Logical Approach to Discrete Math, New York: Springer, p. 423–460, doi:10.1007/978-1-4757-3837-7. See p. 437: " is known as the utility graph".
  4. ^ a b Kullman, David (1979), "The utilities problem", Mathematics Magazine, 52 (5): 299–302, JSTOR 2689782
  5. ^ a b Dudeney, Henry (1917), "Problem 251 – Water, Gas, and Electricity", Amusements in mathematics, Thomas Nelson, p. 73. The solution given on pp. 200–201 involves passing a line through one of the other houses.
  6. ^ Dudeney, Henry (1913), "Perplexities, with some easy puzzles for beginners", The Strand Magazine, vol. 46, p. 110
  7. ^ "Puzzle", Successful Farming, vol. 13, p. 50, 1914; "A well and house puzzle", The Youth's Companion, vol. 90, no. 2, p. 392, 1916.
  8. ^ "32. The fountain puzzle", The Magician's Own Book, Or, The Whole Art of Conjuring, New York: Dick & Fitzgerald, 1857, p. 276
  9. ^ Henneberg, L. (1908), "Die graphische Statik der starren Körper", Encyklopädie der Mathematischen Wissenschaften, vol. 4.1, pp. 345–434. As cited by Coxeter (1950). See in particular p. 403.
  10. ^ a b Dixon, A. C. (1899), "On certain deformable frameworks", Messenger of Mathematics, 29: 1–21, JFM 30.0622.02
  11. ^ Thomsen, Julius (July 1886), "Die Constitution des Benzols" (PDF), Berichte der deutschen chemischen Gesellschaft, 19 (2): 2944–2950, doi:10.1002/cber.188601902285
  12. ^ a b Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5, MR 0038078
  13. ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fundamenta Mathematicae (in French), 15: 271–283
  14. ^ Ayres, W. L. (1938), "Some elementary aspects of topology", The American Mathematical Monthly, 45 (2): 88–92, doi:10.1080/00029890.1938.11990773, JSTOR 2304276, MR 1524194
  15. ^ Trudeau, Richard J. (1993), Introduction to Graph Theory, Dover Books on Mathematics, New York: Dover Publications, pp. 68–70, ISBN 978-0-486-67870-2
  16. ^ Kappraff, Jay (2001), Connections: The Geometric Bridge Between Art and Science, K & E Series on Knots and Everything, vol. 25, World Scientific, p. 128, ISBN 9789810245863
  17. ^ Little, Charles H. C. (1976), "A theorem on planar graphs", in Casse, Louis R. A.; Wallis, Walter D. (eds.), Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference Held at the University of Adelaide August 27–29, 1975, Lecture Notes in Mathematics, vol. 560, Springer, pp. 136–141, doi:10.1007/BFb0097375, MR 0427121
  18. ^ Harary, F. (1964), "Recent results in topological graph theory", Acta Mathematica, 15: 405–411, doi:10.1007/BF01897149, MR 0166775; see p. 409.
  19. ^ Parker, Matt (2015), Things to Make and Do in the Fourth Dimension: A Mathematician's Journey Through Narcissistic Numbers, Optimal Dating Algorithms, at Least Two Kinds of Infinity, and More, New York: Farrar, Straus and Giroux, pp. 180–181, 191–192, ISBN 978-0-374-53563-6, MR 3753642
  20. ^ Larsen, Mogens Esrom (1994), "Misunderstanding my mazy mazes may make me miserable", in Guy, Richard K.; Woodrow, Robert E. (eds.), Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986, MAA Spectrum, Washington, DC: Mathematical Association of America, pp. 289–293, ISBN 0-88385-516-X, MR 1303141. See Figure 7, p. 292.
  21. ^ Pach, János; Sharir, Micha (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127
  22. ^ Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, MR 1220613
  23. ^ Streinu, Ileana (2005), "Pseudo-triangulations, rigidity and motion planning", Discrete & Computational Geometry, 34 (4): 587–635, doi:10.1007/s00454-005-1184-0, MR 2173930. See p. 600: "Not all generically minimally rigid graphs have embeddings as pseudo-triangulations, because not all are planar graphs. The smallest example is ".
  24. ^ a b Walter, D.; Husty, M. L. (2007), "On a nine-bar linkage, its possible configurations and conditions for paradoxical mobility" (PDF), 12th World Congress on Mechanism and Machine Science (IFToMM 2007)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Three_utilities_problem&oldid=1051555418"