Three utilities problem

A puzzle asks whether three houses can each be connected to three utilities by paths that do not cross. Such connections cannot be drawn in the plane because they would form the nonplanar graph K₃,₃.

Connect

K₃,₃: The complete bipartite graph with three vertices in each part and all nine cross-part edges. The nine required connections make the puzzle's graph exactly K₃,₃.
William Rowan Hamilton: An Irish mathematician who made major contributions to mechanics, algebra, and geometry. A related nineteenth-century puzzle tradition helped popularize recreational graph problems.
Network topology: The study of structural properties of networks that remain unchanged under continuous deformation. The puzzle isolates a topological obstruction in a small network.
K₅: The complete graph on five vertices, with an edge between every pair. K₅ is the other minimal forbidden graph in Kuratowski's theorem.
Planar graph: A graph that can be drawn in the plane with edges meeting only at shared endpoints. The puzzle asks whether K₃,₃ is planar; it is not.
Henry Ernest Dudeney: An English puzzler known for mathematical and geometric puzzles published in newspapers and books. His puzzle writing helped bring the utilities problem into popular circulation.
Circuit layout: The arrangement of electronic components and conductive paths on a circuit board or chip. Crossing constraints make the puzzle analogous to routing connections in planar circuit layouts.
Planar graph coloring: The assignment of colors to graph vertices so adjacent vertices receive different colors. Coloring concerns labels on a planar drawing, not whether its edges can cross.
Kuratowski's theorem: A finite graph is planar exactly when it contains no subdivision of K₅ or K₃,₃. It identifies the graph underlying the puzzle as a certificate of nonplanarity.
Sam Loyd: An American puzzle maker and chess problem composer known for widely circulated recreational puzzles. His puzzle culture helped establish the utilities question as a classic challenge.