info prev up next book cdrom email home

Utility Graph


The utility problem asks, ``Can a Planar Graph be constructed from each of three nodes (`house owners') to each of three other nodes (`wells')?'' The answer is no, 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 ${\it UG}$ is the graph showing the relationships described above. It is identical to the Thomsen Graph and, in the more formal parlance of Graph Theory, is known as the Complete Bipartite Graph $K_{3,3}$.

See also Complete Bipartite Graph, Kuratowski Reduction Theorem, Planar Graph, Thomsen Graph


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.

Ore, Ø. Graphs and Their Uses. New York: Random House, pp. 14-17, 1963.

Pappas, T. ``Wood, Water, Grain Problem.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 175 and 233, 1989.

© 1996-9 Eric W. Weisstein