Why is it impossible to connect 3 black dots to 3 red dots?

This is a problem I've thought about quite a bit too and here is my "proof" for why it cannot be done

Further reading

It has to do with graph theory and non-planar graphs.

If (and only if) a graph is planar, you can draw it on a flat piece of paper without the lines ever crossing.

On the other hand, Kuratowski's theorem states that a finite graph is planar if (and only if) it doesn't contain the K5 graph or the K3,3 graph in any form.

The K5 graph is the completely connected graph with 5 nodes. The K3,3 graph is the complete bipartite graph with 3 nodes on either side, which is also known as "the utility graph" because of this very puzzle. (It's usually given in the form of connecting utilities to houses.)

So this puzzle asks you to draw one of the two "archetypal" non-planar graphs, and therefore it's impossible to solve it on a flat piece of paper. Which is why some silly guys "fixed" the puzzle by printing it on a mug. :-)

While hexomino's answer gives a very nice proof from geometric principles, there is a somewhat fast way to see this: simply put, this is impossible because there are too many lines to draw. Especially for mathematicians already familiar with some graph theory, this can serve as a very fast way to solve the problem, but I will expand the theory to, as much as possible, be accessible to all.

---

This fact follows from something called the "Euler characteristic." Basically, suppose you create a figure obeying the following rules:

1. You draw some set of points called vertices.

2. You draw a set of curves called edges, each of which begins and ends at a vertex and does not intersect itself or any other edge.

3. No pair of edges connect the same pair of vertices.

4. It is possible to get from any vertex to any other vertex by following some series of edges.

Such a figure is called a connected planar graph. You'll note that such a graph determines a set of faces, which are just the regions cut out by the edges - including one face representing "the outside". If you let $V$ be the number of vertices and $E$ be the number of edges and $F$ be the number of faces, you have the following relation: $$V-E+F=2$$ I won't go into the proof because, while it's straightforward, it's hard to phrase without mathematical jargon - you can try it out, though! Draw any figure according to these rules and this relation will hold. (This is also a standard fact, subject to proofs in standard sources, such as those that appear via Google)

Another property sometimes called the faceshake lemma is that, if you define the degree of a face to be the number of edges bordering the face, then the sum of the degrees of the faces is twice the number of edges, since each edge borders exactly two faces. Note that the edges on the boundary of any face form a cycle - that is, if you traverse them, you end up back where you started. Since the shortest cycle in the desired graph has length $4$, every face would have to have at least four edges around it; this means we have the relation $$4Fleq 2E$$ since the sum of the degrees of the faces is at least $4F$.

Now, we put things together: we are supposed to draw a graph with $6$ vertices and $9$ edges. There must be no more than $4$ faces, for the faceshake lemma to hold. However, $6-9+F$ is supposed to equal $2$, which means that $F$ should equal $5$. This is a problem because $5>4$ - so there is no way to do it!

Simple proof of impossibility:

The problem can be reduced to the following scenario:

where:

As many have mentioned, there is no "inside the box" answer to the problem.

Depending on the exact statement of the problem, there may be trick answers. For example, as stated, the lines may not touch, but there is no rule against a line going through another circle in the middle of its route.