3 Utilities | 3 Houses puzzle?

Question

There's a puzzle where you have 3 houses and 3 utilities. You must draw lines so that each house is connected to all three utilities, but the lines cannot overlap. However, I'm fairly sure that the puzzle is impossible. How is this proved?

Answer 1

It's not hard to see this is impossible. Connect two houses to the three utilities, and you will essentially have a square with one diagonal drawn. The two corners joined are two of the houses, the other two corners and the midpoint of the diagonal are the utilities. (The actual shape may look distorted from this, but it is essentially this).

Where is the third house? If the house is "outside" the square, you cannot connect it to the utility in the middle. If the house is inside the square, then it is on one of the two sides of the diagonal, and therefore you cannot connect it to the vertex (utility) that is "across" the diagonal.

Postscript. As Aryabhata points out, I am implicitly using the Jordan curve theorem which says that a simple closed curve divides the plane into two disjoint regions, so that any path joining a point from the "outside" to a point "inside" has to cross the boundary. I use it when I argue that the house "outside" cannot be connected to the utility "inside" (without crossing the lines), or that you cannot go from one side of the diagonal to the other without crossing the diagonal.

Answer 2

So, the question seems to be asking for an embedding of $K_{3,3}$ in the plane. This is well-known to be impossible. But, we live on a sphere, rather than a plane. However, it's also impossible in this case, which we can visualise using stereographic projection. You can get pretty close, $K_{3,3} \setminus e$ is planar (i.e. delete an edge).

But... thinking outside the box, there are situations where it is possible:

• We live in three dimensions, where an embedding of $K_{3,3}$ is easily possible.
• There doesn't seem to be anything to prevent one of the utilities also being a house. So in the following graph, red vertices are utilities, blue vertices are houses and the green vertex is both a house and a utility.

Answer 3

Being able to draw in the plane without edges crossing is the property of planar graphs.

That you cannot solve the puzzle follows readily from the following theorem on planar graphs

If $G(V,E)$ is a planar graph and has no cycles of length $3$, then $|E| \le 2|V| - 4$.

In our case $|V| = 6$ (number of nodes) and we need $|E| = 9$ (number of edges). The graph we have cannot have any triangles, as it is bipartite, and any bipartite graph can only have even length cycles.

The above theorem can be proven using Euler's Formula very easily.

The graph you have is known as $K_{3,3}$ and appears in the statement of Kuratowski's Theorem on planar graphs. This theorem characterizes all planar graphs in terms on forbidding $K_5$ (complete graph on 5 vertices) and $K_{3,3}$ as minors.

Answer 4

Here's a short proof that $K_{3,3}$ is nonplanar. (It's borrowed from Bondy and Murty, Graph Theory with Applications, pp. 144-145.)

Some notation: Let $F$ and $\phi$ denote the set and number, respectively, of faces of a planar embedding of a graph. Let $V$ and $\nu$, denote the set and number, respectively, of vertices of a graph. Let $\epsilon$ denote the number of edges in the graph. Let $d(f)$ denote the degree of the face $f$; i.e., the number of edges incident on $f$. Let $G^*$ denote the dual graph.

Claim: $\sum_{f \in F} d(f) = 2\epsilon$.

Proof: $\sum_{f \in F} d(f) = \sum_{f^* \in V(G^*)} d(f^*) = 2\epsilon^* = 2\epsilon$.

(The first step follows from the fact that faces in $G$ correspond to vertices in $G^*$, the second from the well-known fact that the sum of the vertex degrees of a graph is twice the number of edges, and the last from the fact that edges in $G$ correspond to edges in $G^*$.)

Now, suppose $K_{3,3}$ is planar, and let $G$ be a planar embedding of $K_{3,3}$. Since $K_{3,3}$ has no cut edges and no cycles of length less than four, every face of $G$ must have degree at least four. Thus $$4\phi \leq \sum_{f \in F} d(f) = 2\epsilon = 18.$$ Thus $\phi \leq 4$. But, by Euler's theorem, this means $2 = \nu - \epsilon + \phi \leq 6 - 9 + 4 = 1$, a contradiction.