The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Graph Without Crossing Lines

Date: 7/19/96 at 11:41:42
Subject: Graph Without Crossing Lines

Dear Dr. Math,

there are three houses           1        2           3
there are three utilities       gas	    water      electric

How can you connect the three houses individually to the three 
utilities without crossing your lines?

(You have to draw a line from each house to each of the utilities 
without the lines ever crossing.)


Date: 8/15/96 at 10:51:46
From: Doctor Patrick
Subject: Re: Graph Without Crossing Lines

Hi, sorry to tell you this, but that problem is impossible on most 
normal surfaces.  The only one I know of where it will work is what is 
called a torus--which is basically a doughnut-shaped figure with a 
hole in the center.  

If you can, try the problem again on a surface like that and see what
happens.  Since a torus might be hard to come by, you can cut a hole 
in the center of the paper and allow lines to go onto both sides and 
through the hole onto the other side.  

Why do you think it works in this shape?

-Doctor Patrick,  The Math Forum
 Check out our web site!   
Associated Topics:
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.