Three utilities problem

The Three Utilities Problem is a classic problem in graph theory and combinatorial optimization. It involves connecting three houses to three utility services (like water, electricity, and gas) without any of the utility lines crossing each other. In more formal terms, the problem can be visualized as a bipartite graph where one set contains the three houses and the other set contains the three utilities.