How to prove connecting 3 dots to three squares without overlap is impossible?

2,023

The problem of connecting these points using edges is a Graph-Theoretic Problem. If you are unfamiliar with graph theory, I suggest readng up on it here.

Specifically, we say that a graph is planar if it can be drawn such that no edges overlap, as you are trying to do. Wagner's theorem states that a graph is planar only if it does not contain $K_5$ or $K_{3,3}$ as a minor.

But the graph you're trying to achieve -- connecting every * with every 0 -- is $K_{3,3}$. And every graph is a minor of itself, so the graph you're trying to achieve contains $K_{3,3}$ as a minor, so it is not planar.

You'll probably want to read up on complete graphs to understand this answer. $K_{3,3}$ is the complete bipartite graph on two sets of three vertices.

Share:
2,023

Related videos on Youtube

OneChillDude
Author by

OneChillDude

Updated on August 01, 2022

Comments

  • OneChillDude
    OneChillDude over 1 year

    I was given this problem to solve by a professor who promised an A if anyone could solve it. I'm nearly certain it is impossible, because at some point you have too many vertices and inevitably box yourself in, but I would like to know how to prove it.

    How can you prove that it is impossible to connect every * with every 0 without overlapping lines?

    *    *    *   
    
    0    0    0
    

    EDIT: Professor said you get an A if you solve it, not prove it's impossible. I'm not even in the class, it was my friend's question, I am just curious.

    • MathMajor
      MathMajor over 8 years
      Well, it looks like you will be getting a B then :)
    • Blue
      Blue over 8 years
      So, if I tell you the answer, then do I get the A?
    • Admin
      Admin over 8 years
      Your profs is too old school that he/she doesn't even know there 's something called math stackexchage? Half of the class will get A then.
    • mrf
      mrf over 8 years
      The prof only offered an A for a solution, not necessarily for a proof that it's imposible!
    • achille hui
      achille hui over 8 years
      There are two proof of this in Chapter 5 of Robin. J. Wilson's book "Introduction to graph theory". One is constructive, the other one uses Euler's formula. If you still are not satisfied, you can look at Chapter 4 of Richard Diestel's book "Graph Theory" (GTM 173) which uses topology to prove the same statement rigorously.
    • CiaPan
      CiaPan over 8 years
      The drawing requested is a well-known $K_\{3,3\}$ 'utility graph' en.wikipedia.org/wiki/Water,_gas,_and_electricity which is known to be not planar en.wikipedia.org/wiki/Planar_graph – so the task is impossible.