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 0EDIT: 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.
$\endgroup$ 61 Answer
$\begingroup$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.
$\endgroup$
