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 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 .

**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.

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

1999-05-26