Three utilities problem

Imagine three houses. Each house needs three things. They need water, gas, and light.

You must draw lines to each house. But there is a rule. The lines cannot cross each other!

This is a famous math puzzle. It is a very hard one. You might think you can solve it.

But on a flat piece of paper, you cannot. One line will always hit another.

Some people say the puzzle is very old. It is an impossible task on a flat plane.

Imagine you are a worker. You must connect three houses to three utilities. These utilities are water, gas, and electricity.

You must draw a line from every house to every utility. That makes nine lines in total. There is one big rule. The lines cannot cross each other. You must draw them on a flat surface like a piece of paper.

This is a famous math puzzle. It is often called the three utilities problem. Some people say it is very old. A man named Henry Dudeney wrote about it in 1913. Another man named Sam Loyd may have shared it in 1900.

Can you solve it? On a flat plane, the answer is no. It is an impossible puzzle. You will always have at least one crossing. In math, we say this graph is not planar. A planar graph is one that can be drawn without any lines crossing.

But you can change the rules to win. If you draw the lines on a torus, you can solve it. A torus is a shape like a coffee mug. You can also solve it on a Möbius strip. This is a shape made by twisting a strip of paper.

Imagine you are an engineer in a new town. You have three houses that need three different services. These services are water, gas, and electricity. To do your job, you must draw a path from every house to every utility. This means you need to draw nine separate lines. There is one very important rule to follow. None of these lines are allowed to cross each other. You must draw everything on a flat surface, like a sheet of paper. This task is a famous mathematical puzzle called the three utilities problem.

This puzzle is actually impossible to solve on a flat plane. No matter how hard you try, you will always have a crossing. In math, we call this a non-planar graph. A planar graph is a shape that can be drawn without any lines crossing. The utility graph has six points, which mathematicians call vertices. These six points are split into two groups of three. There are nine lines, or edges, connecting them. Because it is not planar, the minimum number of crossings you will always have is one.

People have been thinking about this puzzle for a very long time. Some researchers say the problem is very ancient. Henry Dudeney wrote about it in a magazine in 1913. He believed the puzzle was much older than gas or electric lights. Another man named Sam Loyd might have published it in 1900. In 1886, a chemist named Julius Thomsen used a similar shape. He used it to study the structure of benzene. Because of his work, the shape is sometimes called the Thomsen graph.

Mathematicians use special rules to prove why the puzzle cannot be solved. One way involves a rule called the Jordan curve theorem. Another way uses a math tool called the Euler formula.

This formula looks at the number of faces or areas created by the lines. For this specific graph, the math simply does not add up to a solution. In 1930, Kazimierz Kuratowski stated that this graph is non-planar. His work helped define which graphs can and cannot be drawn on a flat surface.

Even though you cannot solve it on paper, you can win by changing the rules. You can solve the puzzle if you draw it on a torus. A torus is a surface shaped like a coffee mug. You can also solve it on a Möbius strip, which is a twisted loop of paper. Henry Dudeney also suggested a different way to win. He said you could solve it if lines were allowed to pass through a house. Math is full of these surprises when you change the world around the problem.

The three utilities problem is a famous mathematical puzzle involving connections on a surface. The goal is to connect three houses to three different utility companies. These utilities are often called water, gas, and electricity. To complete the task, you must draw nine separate lines. Each house must have a connection to every single utility. There is one strict rule for this puzzle. None of the nine lines are allowed to cross one another. This must be done on a flat, two-dimensional surface like a sheet of paper.

In the field of topological graph theory, this is a formal problem. Mathematicians describe it using a specific structure called a complete bipartite graph, known as K3,3. This graph has six vertices, which are the points representing houses and utilities. The nine lines are called edges. A graph is called planar if it can be drawn on a plane without any edges crossing. The three utilities problem asks if K3,3 is a planar graph. The answer is no, because K3,3 is a non-planar graph.

There are several ways to prove why this puzzle is impossible. One method uses a case analysis involving the Jordan curve theorem. This theorem describes how a closed loop divides a plane into an inside and an outside. Another method uses the Euler formula to check the math of the shapes. The Euler formula relates the number of vertices, edges, and faces in a planar graph. For a bipartite graph like this one, the number of faces must follow a specific rule. In the utility graph, the math fails to satisfy this inequality. Therefore, the graph cannot be drawn without at least one crossing.

History shows that this puzzle has been around for a very long time. Henry Dudeney published the puzzle in 1913 in The Strand Magazine. He claimed the problem was "as old as the hills." He believed it existed long before electric lighting or gas services. Another puzzle maker, Sam Loyd, may have published it as early as 1900. Some early versions of the problem used three houses and three wells. Others used three houses and three fountains. These older versions often had different rules about where the connections could go.

This specific graph structure also appears in the history of chemistry. In 1886, a chemist named Julius Thomsen used it to study benzene. Because of his research, the utility graph is sometimes called the Thomsen graph. Beyond chemistry, the graph is important in rigidity theory. It is a Laman graph, which is a type of graph used to study structural stability. Specifically, it is the smallest example of a non-planar Laman graph. This means its vertices cannot be moved easily without changing the lengths of the edges.

The utility graph has many unique mathematical properties. It is a cubic graph, meaning every vertex has exactly three neighbors. It is also a triangle-free graph, meaning it has no three-sided loops. Because of these traits, it is known as a (3,4)-cage. This makes it the smallest graph with three neighbors per vertex and a shortest cycle of four. It is also a well-covered graph. This means every maximal independent set in the graph is the same size. In this case, there are only two such sets, which are the two groups of three vertices.

While the puzzle is impossible on a flat plane, you can solve it by changing the surface. If you draw the connections on a torus, the puzzle becomes solvable. A torus is a surface with a genus of one, shaped like a coffee mug. You can also solve it on a Möbius strip. This is a surface made by twisting a strip of paper and joining the ends. Henry Dudeney also suggested a different solution. He noted that the puzzle could be solved if lines were allowed to pass through the houses. These variations show how the shape of a world changes the rules of math.