Definition:Utilities Problem

Definition

The utilities problem is a problem in graph theory as follows:

$3$ households are each to be connected to $3$ civic utilities (the archetypes being water, gas and electricity) in such a way that the conduits do not cross.

This is equivalent to investigating whether the Thomsen graph (that is, the complete bipartite graph $K_{3, 3}$) is planar.

Historical Note

The utilities problem appears first to have been posed by Henry Ernest Dudeney in The Strand Magazine $1913$.

It has become a popular problem in puzzle collections ever since.

Sources

• 1913: Henry E. Dudeney: Perplexities: $146$. -- Water, Gas and Electricity (The Strand Magazine Vol. XLVI: p. 110)