Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

|     |     |
1     2--C--3
|     |     |

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?
share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

(C) The Jordan Curve Theorem


share|cite|improve this answer
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
@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. – Will Jagy May 22 '12 at 3:18
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.