The three utilities problem, also known as water, gas and electricity, is a mathematical puzzle that asks for non-crossing connections to be drawn between three houses and three utility companies on a plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without any of them crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

This puzzle can be formalized as a problem in topological graph theory by asking whether the complete bipartite graph ${\displaystyle K_{3,3}}$, with vertices representing the houses and utilities and edges representing their connections, has a graph embedding in the plane. The impossibility of the puzzle corresponds to the fact that ${\displaystyle K_{3,3}}$ is not a planar graph. Multiple proofs of this impossibility are known, and form part of the proof of Kuratowski's theorem characterizing planar graphs by two forbidden subgraphs, one of which is ${\displaystyle K_{3,3}}$. The question of minimizing the number of crossings in drawings of complete bipartite graphs is known as Turán's brick factory problem, and for ${\displaystyle K_{3,3}}$ the minimum number of crossings is one.

${\displaystyle K_{3,3}}$ is a graph with six vertices and nine edges, often referred to as the utility graph in reference to the problem. It has also been called the Thomsen graph after 19th-century chemist Julius Thomsen. It is a well-covered graph, the smallest triangle-free cubic graph, and the smallest non-planar minimally rigid graph.

A review of the history of the three utilities problem is given by Kullman (1979). He states that most published references to the problem characterize it as "very ancient". In the earliest publication found by Kullman, Henry Dudeney (1917) names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than electric lighting, or even gas". Dudeney also published the same puzzle previously, in The Strand Magazine in 1913. A competing claim of priority goes to Sam Loyd, who was quoted by his son in a posthumous biography as having published the problem in 1900.

Another early version of the problem involves connecting three houses to three wells. It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern numberlink puzzles. Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.

As well as in the three utilities problem, the graph ${\displaystyle K_{3,3}}$ appears in late 19th-century and early 20th-century publications both in early studies of structural rigidity and in chemical graph theory, where Julius Thomsen proposed it in 1886 for the then-uncertain structure of benzene. In honor of Thomsen's work, ${\displaystyle K_{3,3}}$ is sometimes called the Thomsen graph.

The three utilities problem can be stated as follows:

Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections without any of the lines crossing each other?