Henry Ernest Dudeney/Modern Puzzles/156 - Water, Gas and Electricity/Solution

From ProofWiki
Jump to navigation Jump to search

Modern Puzzles by Henry Ernest Dudeney: $156$

Water, Gas and Electricity
It is required to lay on water, gas and electricity from $W$, $G$ and $E$ to each of the three houses $A$, $B$ and $C$, without any pipe crossing another.
Dudeney-Modern-Puzzles-156.png
Take your pencil and draw lines showing how this should be done.
You will soon find yourself landed in difficulties.


Solution

There are some tricksy solutions which involve running the pipes underneath the actual houses, such as the below, which apply to the letter of the law:

Dudeney-Modern-Puzzles-156-solution.png

but the fact is that if you treat the houses and pipes as vertices and edges, the problem has no solution.


Proof

The graph as defined is the complete bipartite graph $K_{3, 3}$.

The problem is equivalent to attempting to prove that $K_{3, 3}$ is a planar graph.

However, from Kuratowski's Theorem, $K_{3, 3}$ is non-planar.

$\blacksquare$


This article is complete as far as it goes, but it could do with expansion.
In particular: Martin Gardner poses the question as to whether it can be drawn without a crossing on a torus, which it can.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Historical Note

Henry Ernest Dudeney, on publishing this puzzle in his Modern Puzzles, claims that the proof of the impossibility of a non-tricksy solution to this puzzle is:

for the first time in a book.

Whether this is true or not remains to be investigated.


This is now known in the field of graph theory as the utilities problem, and this particular non-planar graph is known as the Thomsen graph.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Henry_Ernest_Dudeney/Modern_Puzzles/156_-_Water,_Gas_and_Electricity/Solution&oldid=560864"