The Three Utilities Problem
An Introduction to Euler’s Formula.
The utilities problem is stated as follows:
“Try to install water, gas and electrical lines from Utilities W, G and E to each of the houses A, B and C without any lines crossing each other.”
The problem essentially requires you to:
- connect house A to W, G and E
- connect house B to W, G and E
- connect house C to W, G and E
An attempt is shown below
This does not solve the problem, as there is an intersection between two of the wires.
If you’d like to try to solve the problem, take a few moments before reading on and try it now!
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
If you tried to solve the problem, you’ve probably realized by now that connecting the houses to the utilities without intersections is impossible! Fortunately, Leonhard Euler, a Swiss mathematician discovered a beautiful proof of why.
To explain Euler’s proof to you, I first need to talk a little bit about graph theory.
No, I’m not referring to graphs on the Cartesian plane — I’m referring to a graph as a collection of points connected by vertices (the labelled circles below).
The Utilities Problem you may have just attempted was essentially asking you to create a graph! The houses and utilities are represented as vertices, and the the gas / water / electricity lines are represented as edges (the lines connecting the vertices). Another incorrect solution could be represented as below:
In order to now prove that we can’t represent this graph in a form without any intersecting edges, we need to use Euler’s Formula.
Euler’s Formula states that for any graph which can’t be redrawn in a form such that no edges intersect,
F + V = E + 2, where
V is the number of vertices in the graph- a vertex is a “point” on the graph
E is the number of edges in the graph- an edge connects 2 vertices
F is the number of faces in the graph- a face is a region bounded by edges
Let’s try out this formula with a few graphs that don’t have any intersecting vertices.
In graph G1, which is to the left, there are:
4 vertices
6 edges
4 faces (including the outside)
Using Euler’s formula, v + f = e + 2
v + f = 4 + 4 = 8
e + 2 = 6 + 2 = 8
This graph satisfies the equation, and the graph doesn’t have any intersections.
In Graph G2, which is to the right, there are:
4 vertices
6 edges
4 faces (including the outside)
Using Euler’s formula, v + f = e + 2
v + f = 4 + 4 = 8
e + 2 = 6 + 2 = 8
This graph satisfies the equation, and the graph doesn’t have any intersections.
We can use Euler’s formula to prove that such a graph that satisfies the utilities problem can’t exist. The way we are going to do this contradiction- we are going to assume such a graph exists and show it can’t.
In the utilities problem, there can’t be a face formed by a triangle (face with 3 edges. This is because in order for there to be a triangle, there would have a be an edge connecting 2 utilities or 2 houses. The problem is states that connections can only exist between houses and utilities.
Therefore, the simplest face that can be created is one with four edges.
If it starts on a house, it:
- goes to a utility
- goes to a different house
- -goes to a different utility
- closes the loop by returning to the house
It would look like this-
We know that in an ideal solution, there would be 6 vertices and 9 edges, and the number of faces would satisfy the equation
v + f = e + 2
Using the formula with this information, we get
6 + f = 9 + 2
f = 5
As shown above, the most efficient way of creating faces is using faces that have 4 edges bounding them.
If each of the 5 faces had 4 edges bounding them, it would look something like this
The total number of edges the graph would have being 10.
This is a contradiction!
The problem states that the graph must have 9 edges- 3 from each of the houses to a utility.
Since the most efficient method of creating 5 faces on the graph results in 10 edges, this problem is impossible to solve.
