# Is it impossible to draw an edge from each node A,B,C to each node 1,2,3 without intersection? [duplicate]

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?
-

## marked as duplicate by Gerry Myerson, Arturo Magidin, t.b., mixedmath♦, Zev ChonolesMay 23 '12 at 4:17

You may want to look at this article – André Nicolas May 22 '12 at 3:04
You are essentially asking for a proof that $K_{3,3}$ is nonplanar. See this question for the "three houses connecting to three utilities" version. – Arturo Magidin May 22 '12 at 3:06

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
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. – Arturo Magidin May 22 '12 at 3:08
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. – Arturo Magidin May 22 '12 at 3:21