Three utilities problem

Proof without words: One house is temporarily deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions. Whichever region the deleted house is placed into, the similarly shaded utility is outside the region. By the Jordan curve theorem, a line connecting them must intersect one of the existing lines.

As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other. In other words, the graph ${\displaystyle K_{3,3}}$ is not planar. Kazimierz Kuratowski stated in 1930 that ${\displaystyle K_{3,3}}$ is nonplanar,[15] from which it follows that the problem has no solution. Kullman (1979), however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ ${\displaystyle K_{3,3}}$ ] is non-planar".[2]

One proof of the impossibility of finding a planar embedding of ${\displaystyle K_{3,3}}$ uses a case analysis involving the Jordan curve theorem.[16] In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.[17]

Alternatively, it is possible to show that any bridgeless bipartite planar graph with ${\displaystyle V}$ vertices and ${\displaystyle E}$ edges has ${\displaystyle E\leq 2V-4}$ by combining the Euler formula ${\displaystyle V-E+F=2}$ (where ${\displaystyle F}$ is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (the vertices around each face must alternate between houses and utilities, so each face has at least four edges, and each edge belongs to exactly two faces). In the utility graph, ${\displaystyle E=9}$ and ${\displaystyle 2V-4=8}$ so in the utility graph it is untrue that ${\displaystyle E\leq 2V-4}$. Because it does not satisfy this inequality, the utility graph cannot be planar.[18]

Solution on a Möbius strip

Solution on a torus

A torus allows up to 4 utilities and 4 houses

${\displaystyle K_{3,3}}$ is a toroidal graph, which means that it can be embedded without crossings on a torus, a surface of genus one.[19] These embeddings solve versions of the puzzle in which the houses and companies are drawn on a coffee mug or other such surface instead of a flat plane.[20] There is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities.[21][5] Similarly, if the three utilities puzzle is presented on a sheet of a transparent material, it may be solved after twisting and gluing the sheet to form a Möbius strip.[22]

Another way of changing the rules of the puzzle that would make it solvable, suggested by Henry Dudeney, is to allow utility lines to pass through other houses or utilities than the ones they connect.[3]

The utility graph ${\displaystyle K_{3,3}}$ is a Laman graph, meaning that for almost all placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a rigid motion of the whole plane, and that none of its spanning subgraphs have the same rigidity property. It is the smallest example of a nonplanar Laman graph.[23] Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.[9][24] For general-position embeddings, a polynomial equation describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.[24]

${\displaystyle K_{3,3}}$ is a triangle-free graph, in which every vertex has exactly three neighbors (a cubic graph). Among all such graphs, it is the smallest. Therefore, it is the (3,4)-cage, the smallest graph that has three neighbors per vertex and in which the shortest cycle has length four.[25]

Like all other complete bipartite graphs, it is a well-covered graph, meaning that every maximal independent set has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and are of equal sizes. ${\displaystyle K_{3,3}}$ is one of only seven 3-regular 3-connected well-covered graphs.[26]

Drawing of ${\displaystyle K_{3,3}}$ with one crossing

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither ${\displaystyle K_{3,3}}$ nor the complete graph ${\displaystyle K_{5}}$ as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither ${\displaystyle K_{3,3}}$ nor ${\displaystyle K_{5}}$ as a minor, make use of and generalize the non-planarity of ${\displaystyle K_{3,3}}$.[27]

Pál Turán's "brick factory problem" asks more generally for a formula for the minimum number of crossings in a drawing of the complete bipartite graph ${\displaystyle K_{a,b}}$ in terms of the numbers of vertices ${\displaystyle a}$ and ${\displaystyle b}$ on the two sides of the bipartition. The utility graph ${\displaystyle K_{3,3}}$ may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.[5][28]