Piping three circles to three squares

Question

How I can prove the impossibility of joining three circles to three squares with non-intersecting lines (not strictly straight). Shapes of squares and circles are only representative. Each circle should be piped to each square.

Answer 1

This is an old fact, related more to graph-theory than to game-theory. This is a subpart of the general Kuratowski's Theorem, which says that a graph is nonplanar (meaning it can't be drawn with non-intersecting lines) if and only if it has at least one of two types of special subgraph.

On the left is our graph, which many call $K_{3,3}$, because it has two pairs of $3$ vertices, and each vertex in one pair is connected to all the vertices in the other pair, but not at all to the vertices in its own pair. The other is often called $K_5$, because it's $5$ vertices that are all connected to each other.

So you could appeal to (or look up a proof of) Kuratowski's Theorem.

A much simpler proof uses just the Euler Characteristic, which says $$ v - e + f = 2$$ for planar graphs (that is, graphs that can be drawn without intersecting lines), where $v$ is the number of vertices, $e$ the number of edges, and $f$ is the number of faces, including the external face. This is easily proved from first principles from induction and easily looked up, so I don't prove it here.

In $K_{3,3}$, there are $6$ vertices and $9$ edges. So if it were planar, a planar representation would have $5$ faces. A face is a region bounded by edges with no edges in the middle. Notice that here, any face must have an even number of edges. If an edge starts from a TOP vertex, then it goes to a BOTTOM vertex, to a different TOP vertex. To reconnect to the original, it must first go to the BOTTOM, and then back to the TOP. This is caused by the fact that the TOP vertices only connect to the BOTTOM, and vice versa. In particular, no TOP vertex is connected directly to another TOP vertex. So each face is bounded by at least $4$ edges.

Further, each edge bounds exactly $2$ faces. Since there are $5$ faces with at least $4$ edges, but each edge contributes twice to the faces, there must be at least $5\cdot 4 / 2 = 10$ edges overall for the graph to be planar. But there are only $9$ edges! So it is not planar.