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 there are three cottages on a plane (or sphere) and each needs to be connected to the water, gas, and electricity companies. Without using a third dimension or sending any of the connections through another company or cottage, 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. In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph *K*_{3,3} is planar.^{ [1] } This graph is often referred to as the **utility graph** in reference to the problem;^{ [2] } it has also been called the **Thomsen graph**.^{ [3] }

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, HenryDudeney ( 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 *K*_{3,3}. 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.^{ [1] }

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 *K*_{3,3} is not planar. Kazimierz Kuratowski stated in 1930 that *K*_{3,3} is nonplanar,^{ [10] } from which it follows that the problem has no solution. Kullman, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ *K*_{3,3} is ] non-planar".^{ [4] }

One proof of the impossibility of finding a planar embedding of *K*_{3,3} uses a case analysis involving the Jordan curve theorem. 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.^{ [11] }

Alternatively, it is possible to show that any bridgeless bipartite planar graph with V vertices and E edges has *E* ≤ 2*V*− 4 by combining the Euler formula *V*−*E* + *F* = 2 (where F 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, *E* = 9 and 2*V* − 4 = 8, violating this inequality, so the utility graph cannot be planar.^{ [12] }

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither *K*_{3,3} nor the complete graph *K*_{5} as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither *K*_{3,3} nor *K*_{5} as a minor, make use of and generalize the non-planarity of *K*_{3,3}.

K_{3,3} is a toroidal graph, which means it can be embedded without crossings on a torus. In terms of the three cottage problem this means the problem can be solved by punching two holes through the plane (or the sphere) and connecting them with a tube. This changes the topological properties of the surface and using the tube allows the three cottages to be connected without crossing lines. An equivalent statement is that the graph genus of the utility graph is one, and therefore it cannot be embedded in a surface of genus less than one. A surface of genus one is equivalent to a torus. A toroidal embedding of *K*_{3,3} may be obtained by replacing the crossing by a tube, as described above, in which the two holes where the tube connects to the plane are placed along one of the crossing edges on either side of the crossing. Another way of changing the rules of the puzzle is to allow utility lines to pass through the cottages or utilities; this extra freedom allows the puzzle to be solved.

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 *K*_{a,b} in terms of the numbers of vertices *a* and *b* on the two sides of the bipartition. The utility graph *K*_{3,3} may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.^{ [13] }

The utility graph *K*_{3,3} is a circulant graph. It is the (3,4)-cage, the smallest triangle-free cubic graph.^{ [3] } 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. *K*_{3,3} is one of only seven 3-regular 3-connected well-covered graphs.^{ [14] }

It is also a Laman graph, meaning that it forms a minimally rigid system when it is embedded (with crossings) in the plane. It is the smallest example of a nonplanar Laman graph, as the other minimal nonplanar graph, *K*_{5}, is not minimally rigid.

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, **Kuratowski's theorem** is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of *K*_{5} or of *K*_{3,3}.

In the mathematical field of graph theory, a **complete graph** is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A **complete digraph** is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

In the mathematical field of graph theory, the **Petersen graph** is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In graph theory, an **outerplanar graph** is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, an undirected graph *H* is called a **minor** of the graph *G* if *H* can be formed from *G* by deleting edges and vertices and by contracting edges.

In the mathematical field of graph theory, a **complete bipartite graph** or **biclique** is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In topological graph theory, a mathematical discipline, a **linkless embedding** of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked. A **flat embedding** is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A **linklessly embeddable graph** is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an **intrinsically linked graph** is a graph that does not have a linkless embedding.

In mathematics, **topological graph theory** is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs.

In the mathematical discipline of graph theory, the **dual graph** of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, **Wagner's theorem** is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither *K*_{5} nor *K*_{3,3}. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In graph theory, a **book embedding** is a generalization of planar embedding of a graph to embeddings into a *book*, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the *spine*, and the edges are required to stay within a single half-plane. The **book thickness** of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called **pagenumber**, **stacknumber** or **fixed outerthickness**. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In mathematics, **Fáry's theorem** states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

In graph theory, the **Möbius ladder***M*_{n} is a cubic circulant graph with an even number *n* of vertices, formed from an *n*-cycle by adding edges connecting opposite pairs of vertices in the cycle. It is so-named because *M*_{n} has exactly *n*/2 4-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by Guy and Harary (1967).

In graph theory, the **planarity testing** problem is the algorithmic problem of testing whether a given graph is a planar graph. This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(*n*) time, where *n* is the number of edges in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

In mathematics, the **graph structure theorem** is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

In the mathematics of graph drawing, **Turán's brick factory problem** asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

**Barnette's conjecture** is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

In graph theory, a branch of mathematics, an **apex graph** is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is *an* apex, not *the* apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs *K*_{5} or *K*_{3,3}, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In graph theory, the **Kelmans–Seymour conjecture** states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph *K*_{5}. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof has been announced but not yet published.

- 1 2 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*K*_{3,3}on a plane surface without crossings". - ↑ Utility Graph from
*mathworld.wolfram.com* - 1 2 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 . - 1 2 Kullman, David (1979), "The Utilities Problem",
*Mathematics Magazine*,**52**(5): 299–302, JSTOR 2689782. - ↑ Dudeney, Henry (1917), "Problem 251 – Water, Gas, and Electricity",
*Amusements in mathematics*, Thomas Nelson - ↑ Dudeney, Henry (1913), "Perplexities, with some easy puzzles for beginners",
*The Strand Magazine*, vol. 46, p. 110. - ↑ "Puzzle",
*Successful Farming*, vol. 13, p. 50, 1914; "A well and house puzzle",*The Youth's Companion*, vol. 90 no. 2, p. 392, 1916. - ↑ "32. The fountain puzzle",
*The Magician's Own Book, Or, The Whole Art of Conjuring*, New York: Dick & Fitzgerald, 1857, p. 276. - ↑ Henneberg, L. (1908), "Die graphische Statik der starren Körper",
*Encyklopädie der Mathematischen Wissenschaften*,**4.1**, pp. 345–434. As cited by Coxeter (1950). See in particular p. 403. - ↑ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF),
*Fund. Math.*(in French),**15**: 271–283. - ↑ Trudeau, Richard J. (1993),
*Introduction to Graph Theory*(Corrected, enlarged republication. ed.), New York: Dover Pub., pp. 68–70, ISBN 978-0-486-67870-2 , retrieved 8 August 2012 - ↑ Kappraff, Jay (2001),
*Connections: The Geometric Bridge Between Art and Science*, K & E Series on Knots and Everything,**25**, World Scientific, p. 128, ISBN 9789810245863 . - ↑ 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,**152**, American Mathematical Society, pp. 126–127. - ↑ 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 .

- 3 Utilities Puzzle at Cut-the-knot
- The Utilities Puzzle explained and "solved" at Archimedes-lab.org
- Loy, Jim,
*Proof That the Impossible Puzzle is Impossible*, archived from the original on 2007-01-20 - Weisstein, Eric W., "Utility graph",
*MathWorld*

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.