Three utilities problem: Difference between revisions

Revision as of 16:28, 28 November 2021

Revision as of 07:38, 30 November 2021

Line 21:

[[File:3_utilities_problem_proof.svg|thumb|[[Proof without words]]: One house is temporarily deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions. Whichever region the deleted house is placed into, the similarly shaded utility is outside the region. By the [[Jordan curve theorem]], 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 <math>K_{3,3}</math> is not planar. [[Kazimierz Kuratowski]] stated in 1930 that <math>K_{3,3}</math> is nonplanar,{{r|kuratowski}} from which it follows that the problem has no solution. {{harvtxt|Kullman|1979}}, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ <math>K_{3,3}</math> ] is non-planar".{{r|kullman1979}}

One proof of the impossibility of finding a planar embedding of <math>K_{3,3}</math> uses a case analysis involving the [[Jordan curve theorem]].{{r|ayres}} In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.{{r|trudeau}}

Alternatively, it is possible to show that any [[bridgeless graph|bridgeless]] [[bipartite graph|bipartite]] planar graph with <math>V</math> vertices and <math>E</math> edges has <math>E\le 2V-4</math> by combining the [[Euler characteristic|Euler formula]] <math>V-E+F=2</math> (where <math>F</math> is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (the vertices around each face must alternate between houses and utilities, so each face has at least four edges, and each edge belongs to exactly two faces). In the utility graph, <math>E=9</math> and <math>2V-4=8</math>, violatingso in the utility graph it is untrue that <math>E\le 2V-4</math>. Because it does not satisfy this inequality, so the utility graph cannot be planar.{{r|kappraff}}{{Clear|left}}

===Changing the rules===