Associated Topics || Dr. Math Home || Search Dr. Math

### Water, Gas, Electricity to Three Homes Puzzle

```Date: 06/30/2002 at 01:15:50
From: Sam Brownfield
Subject: water gas electricity to 3 homes puzzle

This is a puzzle that I have tried over and over and over to try to
get.  You have the three letters W G E  arranged in any position and
you also have 3 circles (homes) arranged in any position.  You have to
draw a line from each of the W G and E to each of the 3 circles
without crossing lines.  You can put the letter and shapes in any
shape or positions to do this.  I have always got to one line left
over and over and over.  I believe that this is an impossible one to
solve.  If you figure it out, can you tell me what order you put down
the lines since that's half of how you do the problem.

0   W  0  G
E   0       (any position)  I HATE THIS PUZZLE!
```

```
Date: 06/30/2002 at 05:44:29
From: Doctor Anthony
Subject: Re: water gas electricity to 3 homes puzzle

We have 3 utilities A, B, C and 3 houses 1, 2, 3 as shown

A    B    C

1    2    3

and we must join each letter to each number without any of the lines
crossing each other.

This problem comes under the heading of graph theory.

You have probably heard of Euler's formula for plane graphs.  If p =
number of verticies, q = number of edges, r = number of regions then

p - q + r = 2

A plane graph has none of its edges intersecting except at a vertex.

For example, in a square, you have p = 4, q = 4, r = 2 (one region
inside the square, one region outside the square) and

p - q + r = 4 - 4 + 2 = 2   as required.

The proof of Euler's formula is straightforward and can be found in
any textbook on basic graph theory.  We now use it to show that it is
impossible to join the three letters to the three numbers without any
intersections of the edges.

We prove the result by contradiction.  Suppose that it is possible to
draw the figure without any intersections of the edges.

We sum the number of edges lying on the boundary of each region over
all r regions and denote this number by N.  Since no edges join
letters to each other or numbers to each other, the graph contains no
triangles, so it follows that N >= 4r  [To illustrate this, think
again of a square.  The inner region has 4 edges on its boundary.
The outer region has 4 edges on its boundary and so N = 8.  If we had
a triangle then N would be 3+3 = 6 but as stated above there are NO
TRIANGLES.]

On the other hand N counts each edge AT MOST twice (an edge can only
have 1 or 2 regions on either side), so N <= 2q (= 2 x 9 = 18).

We had N >= 4r   so  4r <= N <= 18

r <= 9/2  (=4.5)   ......(1)

However by Euler's formula,  p - q + r = 2

6 - 9 + r = 2

r = 5  ......(2)

Comparing (1) and (2) we see that there is a contradiction and our
assumption that the figure is a plane graph is clearly impossible.

It follows that the letters and numbers cannot be joined without at
least one intersection of two lines.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search