TOPICS
Search

Utility Graph


UtilityGraphs

The utility problem posits three houses and three utility companies--say, gas, electric, and water--and asks if each utility can be connected to each house without having any of the gas/water/electric lines/pipes pass over any other. This is equivalent to the equation "Can a planar graph be constructed from each of three nodes ('houses') to each of three other nodes ('utilities')?" This problem was first posed in this form by H. E. Dudeney in 1917 (Gardner 1984, p. 92).

The answer is that no such planar graph exists, and the proof can be effected using the Jordan curve theorem, while a more general result encompassing this one is the Kuratowski reduction theorem. The utility graph is the graph showing the relationships described above, also known as the Thomsen graph (e.g., Coxeter 1950) and, in the more formal parlance of graph theory, is known as the complete bipartite graph K_(3,3) (and is also equivalent to the circulant graph Ci_6(1,3)).

It is implemented in the Wolfram Language as GraphData["UtilityGraph"].

The utility graph has graph crossing number 1, with a minimal crossing embedding illustrated as the rightmost figure above.

A simple proof of the nonplanarity of the utility graph can be effected by noting that the graph consists of a graph cycle G-A-W-B-E-C, to which the three edges A-E, B-G, and C-W must be added. Now, for each of the edges, we have choose whether to draw the edge inside or outside the graph cycle, and so for two of the edges, we must make the same choice. But two lines can't be drawn on the same side without crossing, hence the graph is not planar.

It can be represented using LCF notation as [-3,3]^3. The utility graph is an integral graph with graph spectrum (-3)^10^43^1.

UtilityGraphMatrices

The plots above show the adjacency, incidence, and graph distance matrices for the utility graph.

Excising an edge of the utility graph gives the tetrahedral graph.

UtilityGraphTorus

The utility graph has graph genus gamma(K_(3,3))=1 and so it can be drawn on a torus with no crossings, as illustrated above (M. Malak, pers. comm., Feb. 15, 2006).


See also

Complete Bipartite Graph, Integral Graph, Kuratowski Reduction Theorem, Planar Graph

Explore with Wolfram|Alpha

References

Chartrand, G. "The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs." §9.1 in Introductory Graph Theory. New York: Dover, pp. 191-202, 1985.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 92-94, 1984.Kullman, D. E. "The Utilities Problem." Math. Mag. 52, 299-302, 1979.Ore, Ø. Graphs and Their Uses. New York: Random House, pp. 14-17, 1963.Royle, G. "F006A." http://www.csse.uwa.edu.au/~gordon/foster/F006A.html.Pappas, T. "Wood, Water, Grain Problem." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 175 and 233, 1989.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 262-263, 1999.

Cite this as:

Weisstein, Eric W. "Utility Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UtilityGraph.html

Subject classifications