3 Utilities | 3 Houses puzzle?

As others have pointed out, you are trying to find a planar representation of the complete bipartite graph $K_{3,3}$ and while there are many proofs that this is not possible, there is one that I find particularly neat.

We will rely on the following results:

  1. $v-e+f=2$ for all planar graphs (see here)

  2. bipartite graphs only contain cycles of even length (see here).

Proof: Let $G$ be a planar graph such that each cycle in $G$ is at least of length 4. Now, each face is just a cycle and since each cycle has at least 4 edges we can establish that $$\frac{4f}{2}\le e$$ whereas we divide by two to avoid double counting (every edge belong to two faces). Rearranging we get $$f\le\frac12 e$$ We can now use Euler's formula to arrive at an inequality that must be satisfied for all planar graphs with cycles of length at least length 4. $$\begin{align*} 2=v-e+f&\le v-e+\frac12e=v-\frac12e\\ \implies 2&\le v-\frac12e \\ \implies e&\le 2v-4 \quad (\spadesuit) \end{align*}$$ Now, in any graph, cycles can be no shorter than length 3 (this follows from the definition of a cycle). However, since $K_{3,3}$ is bipartite each cycle is even and so each cycle is at least of length 4$^*$. We can therefore use ($\spadesuit$) to see if $K_{3,3}$ is planar or not. $K_{3,3}$ has 6 vertices and 9 edges and so: $$9\nleq2(6)-4=8$$ It does not satisfy the inequality and so $K_{3,3}$ cannot be planar. Note that this shows what is so special about that last wire. If you only had 8 wires the inequality would be satisfied $$8\le2(6)-4=8$$

$^*$-Note for this problem you can actually check this for yourself by counting how many edges each cycle in $K_{3,3}$ has.


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).

diagram

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.


In the language of Graph Theory, Graph $K_{3,3}$ is not a planar graph where $K_{m,n}$ is complete bipartite graph.

Definition of Planar Graphs is stated here .

Also as stated, "Kuratowski proved in $1930$ that a graph is planar iff it does not contain within it any graph that is a graph expansion of the complete graph $K_5$ or $K_{3,3}$."