Content deleted Content added
→Properties of the utility graph: intro sentence |
move history to end |
||
Line 5:
|image1=Graph K3-3.svg
|image2=Complex polygon 2-4-3-bipartite graph.png
|total_width=
|footer=Two views of the utility graph, also known as the Thomsen graph or <math>K_{3,3}</math>}}
The classical [[mathematical puzzle]] known as the '''three utilities problem'''; the '''three cottages problem''' or sometimes '''water, gas and electricity''' can be stated as follows:
Line 16:
<math>K_{3,3}</math> is often referred to as the '''utility graph''' in reference to the problem;{{r|gs93}} it has also been called the '''Thomsen graph''' after 19th-century chemist [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]]. It is a [[well-covered graph]], the smallest [[triangle-free graph|triangle-free]] [[cubic graph]], and the smallest non-planar [[Laman graph|minimally rigid graph]]. Although it is nonplanar, it can be drawn with a single crossing, a fact that has been generalized in [[Turán's brick factory problem]], asking for the minimum number of crossings in drawings of other complete bipartite graphs.
==History==▼
A review of the history of the three utilities problem is given by {{harvtxt|Kullman|1979}}. He states that most published references to the problem characterize it as "very ancient".{{r|kullman1979}} In the earliest publication found by Kullman, {{harvs|first=Henry|last=Dudeney|authorlink=Henry Dudeney|year=1917|txt}} names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than [[electric lighting]], or even [[town gas|gas]]".{{r|dud17}} Dudeney also published the same puzzle previously, in ''[[The Strand Magazine]]'' in 1913.{{r|dud13}}▼
Another early version of the problem involves connecting three houses to three wells.{{r|3wells}} It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern [[numberlink]] puzzles.{{r|fountains}}▼
Mathematically, the problem can be formulated in terms of [[graph drawing]]s of the [[complete bipartite graph]] <math>K_{3,3}</math>. This graph▼
makes an early appearance in {{harvtxt|Henneberg|1908}}.{{r|henneberg}} It has six vertices, split into two subsets of three vertices, and nine edges, one for each of the nine ways of pairing a vertex from one subset with a vertex from the other subset.▼
The three utilities problem is the question of whether this graph is a [[planar graph]].{{r|bona}}▼
As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in 19th-century publications both in early studies of [[structural rigidity]]{{r|dixon}} and in [[chemical graph theory]], where [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]] proposed it in 1886 for the then-uncertain structure of [[benzene]].{{r|thomsen}} In honor of Thomsen's work, <math>K_{3,3}</math> is sometimes called the Thomsen graph.{{r|coxeter}}▼
==Puzzle solutions==
Line 53 ⟶ 42:
===Other graph-theoretic properties===
[[File:K33 one crossing.svg|thumb|upright=0.5|Drawing of <math>K_{3,3}</math> with one crossing]]▼
<math>K_{3,3}</math> is a [[triangle-free graph]], in which every vertex has exactly three neighbors (a [[cubic graph]]). Among all such graphs, it is the smallest. Therefore, it is the [[Cage (graph theory)|(3,4)-cage]], the smallest graph that has 3 neighbors per vertex and in which the shortest cycle has length 4.{{r|coxeter}}
Line 61 ⟶ 49:
Two important characterizations of planar graphs, [[Kuratowski's theorem]] that the planar graphs are exactly the graphs that contain neither <math>K_{3,3}</math> nor the [[complete graph]] <math>K_5</math> as a subdivision, and [[Wagner's theorem]] that the planar graphs are exactly the graphs that contain neither <math>K_{3,3}</math> nor <math>K_5</math> as a [[minor (graph theory)|minor]], make use of and generalize the non-planarity of <math>K_{3,3}</math>.{{r|little}}
▲[[File:K33 one crossing.svg|thumb|upright=0.5|Drawing of <math>K_{3,3}</math> with one crossing]]
[[Pál Turán]]'s "[[Turán's brick factory problem|brick factory problem]]" asks more generally for a formula for the [[crossing number (graph theory)|minimum number of crossings]] in a drawing of the [[complete bipartite graph]] <math>K_{a,b}</math> in terms of the numbers of vertices <math>a</math> and <math>b</math> on the two sides of the bipartition. The utility graph <math>K_{3,3}</math> may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.{{r|ps09}}{{Clear|left}}
▲==History==
▲A review of the history of the three utilities problem is given by {{harvtxt|Kullman|1979}}. He states that most published references to the problem characterize it as "very ancient".{{r|kullman1979}} In the earliest publication found by Kullman, {{harvs|first=Henry|last=Dudeney|authorlink=Henry Dudeney|year=1917|txt}} names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than [[electric lighting]], or even [[town gas|gas]]".{{r|dud17}} Dudeney also published the same puzzle previously, in ''[[The Strand Magazine]]'' in 1913.{{r|dud13}}
▲Another early version of the problem involves connecting three houses to three wells.{{r|3wells}} It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern [[numberlink]] puzzles.{{r|fountains}}
▲Mathematically, the problem can be formulated in terms of [[graph drawing]]s of the [[complete bipartite graph]] <math>K_{3,3}</math>. This graph
▲makes an early appearance in {{harvtxt|Henneberg|1908}}.{{r|henneberg}} It has six vertices, split into two subsets of three vertices, and nine edges, one for each of the nine ways of pairing a vertex from one subset with a vertex from the other subset.
▲The three utilities problem is the question of whether this graph is a [[planar graph]].{{r|bona}}
▲As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in 19th-century publications both in early studies of [[structural rigidity]]{{r|dixon}} and in [[chemical graph theory]], where [[Hans Peter Jørgen Julius Thomsen|Julius Thomsen]] proposed it in 1886 for the then-uncertain structure of [[benzene]].{{r|thomsen}} In honor of Thomsen's work, <math>K_{3,3}</math> is sometimes called the Thomsen graph.{{r|coxeter}}
==References==
| |||