Content deleted Content added
Onceinawhile (talk | contribs) image of the problem in a plane. Per WP:DYKIMG, the image "must already be in the article". As discussed at the DYK, this image is more informative than the one without lines. |
Primergrey (talk | contribs) moved history section to the top |
||
Line 13:
<math>K_{3,3}</math> is a graph with six vertices and nine edges, 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]].
==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}} A competing claim of priority goes to [[Sam Loyd]], who was quoted by his son in a posthumous biography as having published the problem in 1900.{{r|early}}▼
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}} Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.{{r|quarrelsome}}▼
As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in late 19th-century and early 20th-century publications both in early studies of [[structural rigidity]]{{r|dixon|henneberg}} 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|bollobas}}▼
==Statement==
Line 58 ⟶ 64:
[[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|early|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}} A competing claim of priority goes to [[Sam Loyd]], who was quoted by his son in a posthumous biography as having published the problem in 1900.{{r|early}}
▲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}} Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.{{r|quarrelsome}}
▲As well as in the three utilities problem, the graph <math>K_{3,3}</math> appears in late 19th-century and early 20th-century publications both in early studies of [[structural rigidity]]{{r|dixon|henneberg}} 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|bollobas}}
==References==
| |||