Why You Cannot Connect 3 Dots to 3 Squares Without Crossings

Title: Why You Cannot Connect 3 Dots to 3 Squares Without Crossings Category: mathematics

The usual interpretation of this puzzle is that each of three dots must be connected to each of three squares. The lines may bend, but they must stay in the plane and may not cross one another except at their endpoints. Under those rules, a crossing-free drawing is impossible, regardless of how cleverly the paths are curved.

The reason is a graph-theory result: the required connections form the complete bipartite graph $K_{3,3}$, which is nonplanar. Here is a short proof using Euler’s formula.

Turn the puzzle into a graph

Represent each dot and each square by a vertex. Draw an edge between a dot and a square whenever the puzzle requires those two shapes to be connected. There are no required connections between two dots or between two squares.

This gives a bipartite graph: its vertices are split into two groups, the three dots and the three squares, and every edge runs between the groups. Since every dot must connect to every square, the graph has all $3\times 3=9$ possible dot-to-square edges. It has six vertices in total.

This graph is called $K_{3,3}$, the complete bipartite graph with three vertices in each part. A drawing with no crossings would be a planar drawing of $K_{3,3}$.

The planar bipartite edge bound

For a connected planar graph, Euler’s formula says

$$v-e+f=2,$$

where $v$ is the number of vertices, $e$ the number of edges, and $f$ the number of regions (faces), including the unbounded outside region.

In a connected, simple bipartite planar graph with at least three vertices, each face boundary has length at least four. A boundary of length three would be a triangle, but a bipartite graph has no odd cycles. Counting edge-sides around all faces counts each edge twice, so

$$4f\leq 2e,$$

and therefore $f\leq e/2$. Substituting this into Euler’s formula gives

$$2=v-e+f\leq v-e+\frac{e}{2}=v-\frac{e}{2}.$$

Rearranging yields the planar bipartite bound

$$e\leq 2v-4.$$

This argument applies to the puzzle’s graph: $K_{3,3}$ is connected, simple, and bipartite.

Apply the bound to the puzzle

With $v=6$, a planar bipartite graph can have at most

$$e\leq 2(6)-4=8$$

edges. But the puzzle requires nine connections. Thus $K_{3,3}$ cannot be planar, and at least one crossing is unavoidable.

The contradiction does not depend on putting the dots or squares in a particular arrangement. Moving the shapes or making the connection paths wavy cannot change the number of vertices and required edges, so it cannot evade the bound.

Common mistakes

• Counting only the three connections in one direction. There are three dots and three squares, and every dot connects to every square, so there are nine connections—not three or six.
• Assuming straight lines are the issue. The proof rules out all continuous paths in the plane, including paths with bends.
• Allowing a route to pass through another shape. In the standard puzzle, a connection may meet another connection only at a shared endpoint. Passing through a non-endpoint or sharing a segment changes the drawing rules.
• Confusing crossings with shared endpoints. Edges that meet at one of the six intended shapes do not count as crossings. The obstruction concerns intersections between paths away from their endpoints.

If the puzzle allows a third dimension, a tunnel, or a connection drawn on the other side of a surface, the planar obstruction no longer applies. The impossibility is specifically about drawing all nine connections in a flat plane without crossings.