Utility Graph

The utility problem asks, ``Can a Planar Graph be constructed from each of three nodes (`house owners') to each ofthree 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 moreformal 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.

• Perimeter Polynomial
• Period Doubling
• Periodic Function
• Periodic Point
• Periodic Sequence
• Period Three Theorem
• Perkins' Quilt
• Perko Pair
• Permanence of Algebraic Form
• Permanence of Mathematical Relations Principle
• Permanent
• Permil
• Permutation
• Permutation Group
• Permutation Matrix
• Permutation Pseudotensor
• Permutation Symbol
• Permutation Tensor
• Peron Integral
• Perpendicular
• Perpendicular Bisector
• Perpendicular Foot
• Perrin Pseudoprime
• Perrin Sequence
• Perron-Frobenius Operator