A problem on finding the no. of impossible connections in a plane of utilities and houses.

Question

There's a puzzle where you have 3 houses and 3 utilities. You must draw lines so that each house is connected to all three utilities, but the lines cannot overlap or cannot go through any house/utility. This question has been asked before but all the questions were proof that this is impossible on a plane.

So as we can see with 3 houses and 3 utilities, 1 connection out of the $3^3$ ideal connections is not possible in this case. My question is, for given any no. of houses and any no. of utilities, how to find the no. of connections that are not possible?

Answer 1

The fundamental theorem of graphs that can be embedded on the plane or sphere is Kuratowski's theorem. To describe it casually, it says that this "utility graph" (which is commonly called $K_{3,3}$ in the field) and the graph formed from five points that are all connected to one another ($K_5$) are the only primitive examples of graphs that are non-planar. That is, if you have a graph that is not planar, then you can erase edges until you have a graph that essentially looks like either $K_5$ or $K_{3,3}$.

So, to answer your direct question, any graph like you describe with more than two houses and more than two utilities will be non-planar. But if you have either one or two houses or either one or two utilities, you can connect them without overlap.

Answer 2

A bipartite planar graph on $n$ vertices (that is, a graph where all edges go between two parts, such as the utility graph where all edges go from houses to utilities) can contain at most $2n-4$ edges. (See this answer for a proof.)

In your problem, if there are $x$ houses and $y$ utilities, then there are $x+y$ vertices. If crossings are forbidden, then out of the $xy$ total connections, at most $2(x+y)-4$ are possible to draw.