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 may want to look at [this article](http://en.wikipedia.org/wiki/Water,_gas,_and_electricity)2012-05-22
  • 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