Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
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
12  
This is a well-known (Within mathematical circles) problem that can be shown to be impossible e.g. here: mathforum.org/dr.math/faq/faq.3utilities.html –  Tom Oldfield May 31 at 11:52
47  
It's easy! Connect to electricity and water. Then use WIFI for the internet! –  Fred Kline May 31 at 11:52
2  
Thank you @TomOldfield I will check it out.... @ Fred lol ;) wifi wasn't around when I was small ;) –  M.S.E May 31 at 11:57
4  
I think that An Elementary Proof That The Utilities Puzzle Is Impossible (2002) by Chris Lomont may be what you are looking for. –  Nico Oct 15 at 14:18

10 Answers 10

up vote 10 down vote accepted

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.

share|improve this answer
1  
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
3  
Maybe you should mention the Jordan Curve Theorem ;-) –  Aryabhata Dec 18 '10 at 1:25
1  
Interestingly, apparently, there is a proof (en.wikipedia.org/wiki/Jordan_curve_theorem#CITEREFThomassen1992) of the Jordan Curve theorem which relies on $K_{3,3}$ being non-planar! –  Aryabhata Dec 18 '10 at 6:26

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.

share|improve this answer

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}$."

share|improve this answer
6  
Do you mean $K_{3,3}?$ Also, could you expand on that? Someone who doesn't know about this problem probably doesn't know what $K_{n,m}$ is, or what it means for a graph to be planar. You also haven't actually shown anything, you've just made a statement equivalent to saying that it is not possible. Could you add a proof that it is not planar, for example? –  Tom Oldfield May 31 at 12:27
    
You can look at this : nomachetejuggling.com/2011/10/29/… –  Manuel Lafond May 31 at 15:58
2  
@manuellafond: The first 'proof' given there is just hand-waving and the second 'proof' using Euler's formula is no better since it's far from trivial to prove Euler's formula for arbitrary planar embeddings with Jordan curves, or equivalently to prove that every planar embedding can be converted into one using straight line segments. –  user21820 May 31 at 17:26

In the book Amusements in Mathematics [4] [9], Henry Ernest Dudeney noted:

“There are some half-dozen puzzles, as old as the hills, that are perpetually cropping up, and there is hardly a month in the year that does not bring inquiries as to their solution. Occasionally one of these, that one had thought was an extinct volcano, bursts into eruption in a surprising manner. I have received an extraordinary number of letters respecting the ancient puzzle that I have called ‘Water, Gas, and Electricity’”.

As this interesting problem − which may be succinctly re-stated as “Can a planar graph be constructed from each of three nodes (‘houses’) to each of three other nodes (‘utilities’)?” [8] − “cropped up” on this website too, it seems profitable to list some references on the topic.

In particular, in response to the request of an intuitive easy to grasp (and almost maths-free) ‘proof’ that the graph $K_{3,3}$ is nonplanar, I would suggest going through Chris Lomont’s An Elementary Proof That The Utilities Puzzle Is Impossible [6].


References:

[1] Alexander Bogomolny, 3 Utilities Puzzle: Water, Gas, Electricity, in ‘Interactive Mathematics Miscellany and Puzzles’: http://www.cut-the-knot.org/do_you_know/3Utilities.shtml.

[2] John Adrian Bondy and U. S. R. Murty, Graph Theory With Applications, Elsevier Science Publishing, New York, 1976, pp. 144-145.

[3] Harold Scott MacDonald Coxeter, Self-dual configurations and regular graphs, in ‘Bulletin of the American Mathematical Society’ 56 (5), 1950, pp. 413-455.

[4] Henry Ernest Dudeney, Amusements in Mathematics, Thomas Nelson and Sons, London, 1917, pp. 73, 200-201.

[5] David Kullman, The Utilities Problem, in ‘Mathematics Magazine’ 52 (5), 1979, pp. 299-302.

[6] Chris Lomont, An Elementary Proof That The Utilities Puzzle Is Impossible, 2002: http://www.lomont.org/Math/Papers/2002/K33.pdf.

[7] Øystein Ore and Robin J. Wilson (editor), Graphs and their Uses, The Mathematical Association of America, Washington, 1990.

[8] Eric W. Weisstein, Utility Graph, in ‘MathWorld’ − A Wolfram Web Resource: http://mathworld.wolfram.com/UtilityGraph.html.

[9] David Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, New York, 1992, p. 101.

[10] Wikipedia contributors, Water, gas, and electricity, in ‘Wikipedia, The Free Encyclopedia’: http://en.wikipedia.org/w/index.php?title=Water,_gas,_and_electricity&oldid=623969177.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

This is a sketch as to why it is impossible which you may (or may not) be interested in:

If you are going to solve your proposed problem, most certainly you'd have to connect each house to electricity and water at some point. Imagine someone very clever proposes a solution to the problem, we only ask the person, "How did you connect the three houses to electricity and water?" If they did this successfully, we'll show them there is a problem with the internet.

Draw their partial solution on paper. The fact that the connections do not cross tell us that the paper is divided into 3 sections (each section has a boundary of four edges):

region enclosed by connections from house 1 to electricity to house 2 to water and back to house 1
- section A

region enclosed by connections from house 2 to electricity to house 3 to water and back to house 1
- section B

region enclosed by connections from house 1 to electricity to house 3 to water and back to house 1
- section C

Note that a "section" may go all the way to the end of the paper (indeed one has to). These three sections cover the whole paper (if you include the connections, houses, water and electricity as well).

Suppose the internet is in section A. Then there is no way to get to house 3 without creating a crossing! Indeed house 3 is not in section A so if there was a connection from the internet to house 3, at some point (when it left the section) it must crossed a previous connection. The same argument works if the internet is in section B (no way to get to house 2 without creating a crossing) and section C (no way to get to house 1 without creating a crossing).

share|improve this answer

There are three houses A, B, and C, and three utilities (gas, electric, water) labelled X, Y , and Z. Suppose there is a solution drawn on a rubber sheet with curves connecting AX, AY , AZ, BX, BY,BZ, CX, CY , and CZ, none of which cross except at the endpoints:

enter image description here

Then, just using B, X, Y , and Z, and the connecting curves BX, BY , and BZ, the rubber sheet can be stretched to give:

enter image description here

Then the rubber sheet can be stretched, placing the house C and the curve CY like:

enter image description here

Now for the hardest part to see:

The curve CZ can be stretched into one of two cases:

enter image description here

The leftmost picture (case 1) is clearly one such curve, but it takes some thinking to convince oneself that the rightmost picture (case 2) is the only other possible curve CZ. One way to reason is that the loop BY CZ either encloses X or it does not.


Consider the right case.

There must be a curve CX, and the only possibility is that it can be deformed to give:

enter image description here

Then the house A must be in one of the regions I, II, or III.

If A is in region I it cannot be connected to utility Y by a curve that does not cross any other curve. If A is in II, it cannot connect to Z, and finally if A is in region III, it cannot be connected to X.

So we are left with case 1 only. Stretching the curve CX, we get two cases again (by the same reasoning above - only two curves are possible determined by whether or not Z is inside the loop BY CX):

enter image description here

Place house A on the left diagram. If it is in region I, it cannot connect to Y, if A is in II, it cannot connect to Z, and if A is in region III, it cannot connect to X. The same sentences apply to the right diagram.

Thus all cases have been studied, and the Utilities Puzzle has no solution in the plane. Equivalently the graph $K_{3,3}$ is non-planar.


Reference : Chris Tomont's Elementary Proof to the Three Utility Problem

share|improve this answer
8  
Frankly, I think that you should mention that this is a summary of Chris Lomont's An Elementary Proof That The Utilities Puzzle Is Impossible. –  Nico Oct 15 at 19:22
    
@Nico Done. Did it. –  The Artist Oct 16 at 4:15
    
This is brilliant.....Nico was the first to point this to me :) I hope for more proofs :) –  M.S.E Oct 16 at 11:15

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.

alt text

share|improve this answer

Here is a solution to this problem:

(Gas is Internet in this case)

enter image description here

share|improve this answer
3  
Not acceptable :p –  M.S.E Oct 16 at 14:21
    
He is looking for a planar solution. Ofcourse with a 3d spatial arrangement this is possible. –  mkuse Oct 21 at 8:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.