From: drjjmott@cs.com (Renee)
Subject: 6 dots
Date: 29 Aug 1999 13:11:35 -0400
Newsgroups: sci.math
Keywords: Non-planarity of K_{3,3}

Connect all the bottom dots to the top dots without crossing or
touching each other.



              *          *          *



              *          *          *


What principal, if any, am I looking for?
==============================================================================

From: David <cdl@mindspring.com>
Subject: Re: 6 dots
Date: 29 Aug 1999 21:58:36 GMT
Newsgroups: sci.math

The principle that you are looking for is the planarity of a graph.  A
graph is a planar graph if it can be drawn in the plane without any edges
crossing.

The graph that you are looking at is K(3,3) - the complete bipartite
graph with 3 vertices in each partition.  But it turns out that this
graph is not planar.  (And Hence you can't draw in all 9 edges without
some of them crossing.)

Given the number of vertices (or dots) in your graph, you can calculate
the maximum number of edges (or lines) that the graph can have, and still
be planar:

A simple planar graph with v vertices can have at most 3v-6 edges.

This would suggest that youcould have at most 3(6)-6 = 12 edges on your
graph without any crossing.  However, this would include two edges
between the vertices on top, and two edges between the vertices on the
bottom, so removing those, you are left with only 8 edges - one shy of
the 9 that you need to make all the connections.

Actually, this leads to a further result that a simple planar
triangle-free graph on v vertices can have at most 2v-4 edges.

The puzzle that you are looking at is sometimes called the 3 utility
problem - where the top three dots represent utility companies and the
bottom three dots represent houses, and one tries to find a way to run
each utility to each house without any lines crossing.  Of course, there
is no solution.

I hope this helps.

David