Dr. Math FAQ ||
Classic Problems ||
Formulas ||
Search Dr. Math ||
Dr. Math Home

There are three houses and three utilities:You must draw a line from each house to each utility,
without the lines ever crossing.
The three utilities puzzle can be solved on a special kind of two-dimensional surface. This special place is the outside of a torus. A torus is shaped like a perfect doughnut, with a hole in the middle. You can see a movie of a flat surface becoming a torus at Alexander Bogomolny's page about Paper Strip Activities. Here's one solution: A piece of paper with a hole in it is like a torus that has been squashed flat. This means that the three utilities problem can also be solved by cutting a hole in the center of a piece of paper. Lines are allowed to go around the sides of the paper, or through the hole to the other side.
Using the Jordan Curve Theorem
The Jordan Curve Theorem tells us that the loop will have an inside and an outside no matter how we stretch or curve our lines, as long as they don't cross. Now, we still have three lines left to draw: from house 1 to the water company, house 2 to the gas company, and house 3 to the electric company. Because we don't want to cross the lines we have already drawn, we have to choose whether to draw these new lines inside or outside our loop.
We have already seen vertices, or nodes, and edges: in our problem, the vertices are the houses and utility companies, and the edges are the lines between them. Another important object in graph theory is a "face." Faces in graph theory are a lot like the six faces of a cube. They're the area inside a closed loop of edges. There can't be any vertices in the middle of a face. Leonhard Euler found a formula to relate the number of faces, edges, and vertices in a planar graph: where F is the number of faces, E is the number of edges, and V is the number of vertices. This formula counts the area outside the graph as one of the faces. Now, let's pretend we have a solution to the utility problem. There are six vertices, one for each house and utility company. Because each of the three utility companies is connected to three houses, we have 3 * 3 = 9 edges. Let's see what we can figure out about the faces. We know that the boundary of every face is a closed loop of edges, and we know that every edge goes between a house and a utility company. There's no reason to go from a house to a utility and back to the same house.
Now let's use Euler's formula to figure out how many faces there are: F - E + V = 2 Every face has at least four edges, so the number of edges in all the faces is at least 4 * 5 = 20 edges. This counts each edge twice, because every edge is a boundary for two faces. So, the smallest number of edges is 20 / 2 = 10 edges. However, we know that there are only 9 edges! Since nothing can have nine edges and ten edges at the same time, drawing a solution to the three utilities problem must be impossible. - Utility Graph, Eric Weisstein's World of Mathematics
- 3 Utilities Problem, Alexander Bogomolny
- THE EULER FORMULA, PART II, Micah Fogel
- Connecting Three Utilities to Three Houses, Keith L. Green
## From the Dr. Math archives:## From the Web:- Ursula Whitcher, for the Math Forum |

[**Privacy Policy**]
[**Terms of Use**]

Math Forum Home ||
Math Library ||
Quick Reference ||
Math Forum Search

© 1994-2016 The Math Forum at NCTM. All rights reserved.

http://mathforum.org/