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