0
$\begingroup$

Possible Duplicate:
3 Utilities | 3 Houses puzzle?

I am not sure if this question has been answered, and if that answer is part of Euclidean geometry (single plane/2 dimensional) or a part of Graph Theory.

If you have 3 nodes (A, B, C), is it impossible to draw an edge from each of these 3 nodes to 3 other nodes (1, 2, 3) without any of these edges intersecting?

+-----A-----+ |     |     | 1     2--C--3 |     |     | +-----B-----+ 

From the example above, you cannot draw an edge connecting C to 1, without intersecting one of the previous lines. (I would include a nice graphic, but my reputation won't let me)

  • Has this been proven?
  • If so, what is the name of this theorm?
  • 0
    You are essentially asking for a proof that $K_{3,3}$ is nonplanar. See [this question](http://math.stackexchange.com/q/14723/742) for the "three houses connecting to three utilities" version.2012-05-22

1 Answers 1

1

All proved. Your graph is called $K_{3,3},$ the complete bipartite graph on $3+3$ vertices. It is not planar, something which was surely known to Euler. However, unless you are willing to make restrictions on the graph edges (such as smoothness or, as you have illustrated, piecewise linearity) the following three facts are equivalent, and all difficult:

(A) $K_5$ is not planar

(B) $K_{3,3}$ is not planar

(C) The Jordan Curve Theorem

LINK

  • 0
    Granted, non-planarity of $K_{3,3}$, Euler's formula, and the Jordan Curve Theorem are very close to one another. But the 'hard' part of Kuratowski's Theorem is somewhat in the *other* direction, from non-planarity *to* $K_{3,3}$ (or $K_5$), rather than showing $K_{3,3}$ is non-planar. That's why I thought pointing to Kuratowski was a bit of overkill.2012-05-22