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

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
    Kuratowski's Theorem is much stronger than this... the Jordan Curve theorem, or Euler's formula, are enough to establish $K_{3,3}$ is not planar.2012-05-22
  • 0
    @Arturo, got you. I just felt it fit. We had a very long discussion about planarity on MO. I felt we had agreement that Euler was implicitly using Jordan curve as obvious, and that the three results are equivalent. But there was a very persuasive bit about PL Jordan Curve.2012-05-22
  • 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