3->3 Mapping With No Crossed Lines

Consider 6 points on a plane, labelled A, B, C and X, Y, Z, as shown
below
                       A   B   C

                       X   Y   Z

Is it possible to draw a line from each of A, B, C to each of X, Y,
Z without any of the lines crossing?   

The answer is no.  Such a configuration requires three parallel 
connections between A and B passing through the points X, Y, and Z.  
For any three non-crossing paths connecting two points, one of the 
paths must be contained entirely within the loop formed by the other 
two.  Thus, without loss of generality we can assume that point Z 
is inside the loop AXBYA.
  
Therefore the plane has been partitioned into three empty regions 
bounded by the loops AXBZA, AZBYA, and AXBYA. The point C must fall 
in exactly one of these three regions, which makes it inaccessible to 
Y, X, or Z respectively.

This is actually a consequence of a theorem by Kuratowski which
states that a graph is "planar" (i.e., contains no crossed lines) 
if and only if it contains no subgraph that is congruent with the 
completely connected graph K(5) or with the completely connected 
bi-graph K(3,3).  The latter is the configuration of the given 
problem.

Return to MathPages Main Menu
Сайт управляется системой uCoz