Proof without words: The leftmost house is first deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions, shaded yellow, red and blue. Whichever region the deleted house is placed into, the utility with its colour is outside the region. The Jordan curve theorem states that a line connecting them must intersect one of the existing lines. As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other. In other words, the graph K3,3 is not planar. Kazimierz Kuratowski stated in 1930 that K3,3 is nonplanar,. from which it follows that the problem has no solution. Kullman, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ K3,3 is ] non-planar".
Proof without words: One house is temporarily deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions, shaded yellow, red and blue. Whichever region the deleted house is placed into, the utility similarly coloured is outside the region. The Jordan curve theorem states that a line connecting them must intersect one of the existing lines. As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other. In other words, the graph K3,3 is not planar. Kazimierz Kuratowski stated in 1930 that K3,3 is nonplanar,. from which it follows that the problem has no solution. Kullman, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ K3,3 is ] non-planar".
R
The leftmost house is first
One house is temporarily
R
with its colour
similarly coloured