For anybody that doesn't know what's going on: https://en.wikipedia.org/wiki/Water,_gas,_and_electricity

This can be solved on a torus, no?

To some extent, that's the point. People go "Oh! Three utilities - nice problem - excellent mug."

It's sometimes only much later that people go "Hang on! It can be solved on the mug!"

It's a cool mug.

Yes. K_{3,3} can be embedded on a torus.