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?
3 Utilities | 3 Houses puzzle?
-
6This is equivalent to drawing a *bipartite graph* (http://en.wikipedia.org/wiki/Bipartite_graph) in the plane, specifically $K_{3,3}$. This is impossible due to Kuratowski's theorem (http://en.wikipedia.org/wiki/Kuratowski%27s_theorem#Kuratowski.27s_and_Wagner.27s_theorems), but I don't know the proof. – 2010-12-17
-
0@Kevin Y: You forgot the requirement that the "lines" connecting the houses and the utilities must not intersect. – 2010-12-17
-
0@Arturo Magidin Thanks for catching that, it's quite an important part of the puzzle. :P – 2010-12-17
-
0I seem to remember that it is possible if the graph is on a torus though. Is there a reference to that result? – 2010-12-17
-
1@Raskolnikov: http://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". – 2010-12-17
-
0@Raskolnikov Yes, the puzzle is impossible on a 2D plane but [it *is* possible on a torus](http://mathforum.org/dr/math/faq/images/utilities_torus.gif). – 2010-12-18
-
1@ 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". – 2010-12-18
-
12This is a well-known (Within mathematical circles) problem that can be shown to be impossible e.g. here: http://mathforum.org/dr.math/faq/faq.3utilities.html – 2014-05-31
-
50It's easy! Connect to electricity and water. Then use WIFI for the internet! – 2014-05-31
-
2Thank you @TomOldfield I will check it out.... @ Fred lol ;) wifi wasn't around when I was small ;) – 2014-05-31
-
2@FredKline smart you, but my question is something in 2D and not 3D for wifis to be there ;) – 2014-05-31
-
0when i was child, there were seldom internet connection for homes – 2014-05-31
-
1@FredKline, that was an epic solution +1 for cool! :) – 2014-05-31
-
0Well, technically speaking, it is possible to do it if you allow wires going through houses (as was also mentioned in the link provided by Tom Oldfield and isn't one of your restrictions). But otherwise it is of course well known to be impossible in 2D. – 2014-05-31
-
1When I saw this title I just knew which problem it was. My algebra teacher gave this to me to shut me up and I spent countless hours on it. – 2014-05-31
-
0This is the classic [Three Utilities Puzzle](http://www.cut-the-knot.org/do_you_know/3Utilities.shtml) (Water, Gas, Electrictity), with "Gas" changed to "Internet". – 2014-05-31
-
1Was it a childhood trauma for you? – 2014-05-31
-
0@BillDubuque: The link doesn't prove that Euler's formula works for arbitrary planar embeddings. Do you have a simple elementary proof of that? – 2014-05-31
-
0@Tharindu: happy you found closure, after all these years. – 2014-05-31
-
0@QuoraFeans :) :) :) :) :) – 2014-06-01
-
1I'm still angry that people do this to kids. At least give them a solvable hard problem to do.... – 2014-06-02
-
0In my country, it was a gas connection instead of internet. A gas connection would be better for this problem. – 2014-06-02
-
2@Nick yep gas connection would have been better than internet. – 2014-07-31
-
0This is also called the Utility Problem in Graph Theory. It's probably introduced in the first chapter of many graph theory books. Unfortunately, I can't tell you much about it since I haven't studied it but I thought I would give you the key words so that you can do extra research on it if you want. – 2014-10-15
-
1There was internet when you were a child? You must be very young. – 2014-10-15
-
0@bof yes it was there :) – 2014-10-15
-
0@FredKline (+1) for the epic solution. – 2014-10-15
-
1@Moronplusplus what do you mean ? There are 3 things, it's not about choosing 2 :) – 2014-10-15
-
0But I can't have 3 of them without the wires intersecting. – 2014-10-15
-
0@Moronplusplus I know right :) I would go with water and Internet (a device which has a never ending battery) :) – 2014-10-15
-
0Hahah Wow, I just wish this question gets a super easy explanation and hope kids see this, that would just put an end to child abuse. – 2014-10-15
-
4I think that [*An Elementary Proof That The Utilities Puzzle Is Impossible*](http://www.lomont.org/Math/Papers/2002/K33.pdf) (2002) by Chris Lomont may be what you are looking for. – 2014-10-15
-
0If so, let me know and I will post it as an answer to your question. – 2014-10-15
-
0@Nico , Thank you very much. I am checking this out. Would take a while to read the whole thing, if your sure this is elementary level explanation you can post it right away. I don't think its only me who should understand it and message you whether to post it, so I think you should post it for everyone :) – 2014-10-15
-
0@Nico , Put it as an answer :) – 2014-10-15
-
0In response to your bounty description. You can tell the rich man to draw on paper and show the plan, and if he can draw then you will construct it. Then watch him struggle..... – 2014-10-16
-
1The accepted answer in epimorphic's link seems particularly suitable as far as 'intuition' goes. – 2014-10-20
10 Answers
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.
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:
$v-e+f=2$ for all planar graphs (see here)
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.
-
1Note that Euler's theorem that you are using here cannot be proven in general without using the Jordan curve theorem or equivalent. – 2014-12-23
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.
-
1http://i.imgur.com/RDtnU.png – 2010-12-18
-
0@Américo Tavares: Thanks. – 2010-12-18
-
0The picture in my comment is not very good, but I think you can insert it into your answer, until there is one better. – 2010-12-18
-
0@Américo Tavares: done and done. Thanks again. – 2010-12-18
-
0I chose this as the accepted answer because it's very easy to understand the problem this way. However, all of the other answers are great too! – 2010-12-18
-
4Maybe you should mention the Jordan Curve Theorem ;-) – 2010-12-18
-
1Interestingly, apparently, there is a proof (http://en.wikipedia.org/wiki/Jordan_curve_theorem#CITEREFThomassen1992) of the Jordan Curve theorem which relies on $K_{3,3}$ being non-planar! – 2010-12-18
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}$."
-
6Do 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? – 2014-05-31
-
0You can look at this : http://www.nomachetejuggling.com/2011/10/29/why-the-complete-bipartite-graph-k33-is-not-planar/ – 2014-05-31
-
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. – 2014-05-31
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.
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.
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).
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:
Then, just using B, X, Y , and Z, and the connecting curves BX, BY , and BZ, the rubber sheet can be stretched to give:
Then the rubber sheet can be stretched, placing the house C and the curve CY like:
Now for the hardest part to see:
The curve CZ can be stretched into one of two cases:
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:
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):
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
-
8Frankly, I think that you *should* mention that this is a summary of Chris Lomont's *An Elementary Proof That The Utilities Puzzle Is Impossible*. – 2014-10-15
-
0@Nico Done. Did it. – 2014-10-16
-
0This is brilliant.....Nico was the first to point this to me :) I hope for more proofs :) – 2014-10-16
Here is a fun solution to this problem:
(Gas is Internet in this case)
(As pointed out, this is not what the OP intended)
-
4Not acceptable :p – 2014-10-16
-
0He is looking for a planar solution. Ofcourse with a 3d spatial arrangement this is possible. – 2014-10-21