Three utilities problem: Difference between revisions

Revision as of 19:46, 24 October 2021

Revision as of 19:55, 24 October 2021

Line 42:

===Other graph-theoretic properties===

<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|coxetertutte}}

Like all other [[complete bipartite graph]]s, it is a [[well-covered graph]], meaning that every [[maximal independent set]] has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and obviously they are equal. <math>K_{3,3}</math> is one of only seven [[cubic graph|3-regular]] [[k-vertex-connected graph|3-connected]] well-covered graphs.{{r|cer93}}

Line 57:

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}}

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|coxeterbollobas}}

==References==

Line 75:

| volume = 45

| year = 1938}}</ref>

<ref name=coxeterbollobas>{{citation

| last = Bollobás | first = Béla

| doi = 10.1007/978-1-4612-0619-4

| isbn = 0-387-98488-7

| mr = 00380781633290

| volumepage = 5623

| publisher = Springer-Verlag, New York

| series = Graduate Texts in Mathematics

| title = Modern Graph Theory

| url = https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA23

| volume = 184

| year = 19501998}}</ref>

<ref name=bona>{{citation

Line 94 ⟶ 107:

| volume = 13

| year = 1993}}</ref>

<ref name=coxeter>{{citation

| last = Coxeter | first = H. S. M. | author-link = Harold Scott MacDonald Coxeter

| doi = 10.1090/S0002-9904-1950-09407-5 | doi-access = free

| journal = [[Bulletin of the American Mathematical Society]]

| mr = 0038078

| pages = 413–455

| title = Self-dual configurations and regular graphs

| volume = 56

| year = 1950}}</ref>

<ref name=dixon>{{citation

Line 168 ⟶ 171:

| title = Encyklopädie der Mathematischen Wissenschaften

| volume = 4.1

| year = 1908}}. As cited by {{harvtxt|Coxeter|1950}}. See in particular [https://archive.org/stream/encyklomath104encyrich/#page/n425/mode/2up p.&nbsp;403].</ref>

<ref name=intuitive>{{citation

Line 289 ⟶ 292:

| title = Introduction to Graph Theory

| year = 1993}}</ref>

<ref name=tutte>{{citation

| last = CoxeterTutte | first = HW. S. MT. | author-link = HaroldW. Scott MacDonaldT. CoxeterTutte

| doi = 10.1017/s0305004100023720

| journal = [[BulletinProceedings of the AmericanCambridge MathematicalPhilosophical Society]]

| mr = 21678

| pages = 413–455459–474

| title = A family of cubical graphs

| volume = 43

| year = 1947}}</ref>

<ref name=wh07>{{citation