Problema de los tres servicios

Se conoce como el problema de los tres servicios a un problema matemático clásico que consiste en proporcionar tres servicios: agua, electricidad y gas, a tres casas. Para ello hay que conectar cada uno de los servicios a cada casa con una línea que representa la cañería o los cables. Debemos dar todos los servicios a todas las casas sin que las líneas de conexión se crucen.

En un análisis sobre la historia del problema, realizado por Kullman, declara que la mayoría de las referencias al problema lo caracterizan de "muy antiguo".^[1]​ La publicación más temprana encontrada por Kullman es de Dudeney, y el problema es denominado "agua, gas, y electricidad". Aun así, Dudeney declara que el problema es "tan viejo como las montañas..., mucho más viejo que la luz eléctrica o incluso el servicio de gas".^[2]​ Dudeney También publicó el mismo rompecabezas anteriormente, en "The Strand Magazine" en 1913.^[3]​

El problema es imposible de resolver cuando es presentado en un plano; es decir, no hay ninguna manera de hacer las nueve conexiones sin que alguna de las líneas crucen otra.

Existen soluciones alternativas, realizadas en la superficie de un toroide (ver figura).

El problema puede ser formalizado matemáticamente analizando si el grafo bipartito completo K3,3 es un grafo plano. Kazimierz Kuratowski declaró en 1930 que K3,3 es no planar, por lo que se sigue que el problema no tiene solución.^[4]​

Se puede probar la imposibilidad de encontrar una solución plana de K3,3 es con el Teorema de la curva de Jordan. Este problema también puede demostrarse como imposible de resolver utilizando la Característica de Euler.

Se puede plantear el mismo problema con algunas variantes para que tenga solución:

• Permitiendo un único cruce de líneas.
• Permitiendo pasar un servicio por dentro de una casa.
• Permitiendo usar el reverso de una hoja perforada. (ver gráfico)