3 Utilities | 3 Houses puzzle?

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?

-
This is equivalent to drawing a bipartite graph (en.wikipedia.org/wiki/Bipartite_graph) in the plane, specifically $K_{3,3}$. This is impossible due to Kuratowski's theorem (en.wikipedia.org/wiki/…), but I don't know the proof. –  Aaron Mazel-Gee Dec 17 '10 at 22:49
@Kevin Y: You forgot the requirement that the "lines" connecting the houses and the utilities must not intersect. –  Arturo Magidin Dec 17 '10 at 23:06
@Arturo Magidin Thanks for catching that, it's quite an important part of the puzzle. :P –  Kevin Y Dec 17 '10 at 23:12
@Raskolnikov: sun.cs.lsus.edu/~rmabry/math/rmabry/live3d/k33-torus.htm; or you can draw it on $[0,1]\times[0,1]$ with identified edges. Start with a diamond, with the top and bottom vertices being houses, and the left and right utilities. Put the third utility below the bottom house, and connect it to the top house by going "straight down". Then put the third house left of the leftmost utility, and connect it to the rightmost utility by going "straight left". –  Arturo Magidin Dec 17 '10 at 23:33
@ Aaron: It is impossible by Euler's theorem, as shown in the answers. Kuratowski's theorem is very deep and is to the converse. It says that a graph which is not planar must somehow have a $K_{3,3}$ or a $K_5$ "built in". –  Christian Blatter Dec 18 '10 at 10:26

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.

-
i.imgur.com/RDtnU.png –  Américo Tavares Dec 18 '10 at 0:22
@Américo Tavares: Thanks. –  Arturo Magidin Dec 18 '10 at 0:27
The picture in my comment is not very good, but I think you can insert it into your answer, until there is one better. –  Américo Tavares Dec 18 '10 at 0:30
@Américo Tavares: done and done. Thanks again. –  Arturo Magidin Dec 18 '10 at 0:30
Maybe you should mention the Jordan Curve Theorem ;-) –  Aryabhata Dec 18 '10 at 1:25

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.

-

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.

-

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.

-