#set document(title: "12.7 Hamilton Cycles", author: "OpenStax / XYZ Homework")
#set page(width: 8.5in, height: auto, margin: 1in)
#import "@preview/cetz:0.5.2"
#set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en")
#show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math"))
#set par(justify: true, leading: 0.62em, spacing: 0.9em)
#set enum(spacing: 1.1em)   // room between list items so tall inline fractions don't collide
#set list(spacing: 1.1em)
#set table(stroke: 0.5pt + rgb("#c7ccd3"))

#let BLUE = rgb("#183B6F")     // brand navy — section bars + example/solution labels (white on navy 11.09:1)
#let ORANGE = rgb("#A94509")   // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text)
#let RED = rgb("#DC2626")      // brand error-600
#let GREEN = rgb("#059669")    // brand success-600 (decoration only; small green text uses green-text #007942)

#show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt,
  fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt,
  text(fill: white, weight: "bold", size: 19pt, it.body))
#show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt,
  fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt,
  text(fill: white, weight: "bold", size: 12pt, it.body))
#show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body)
#show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body)

#let examplebox(label, title, body) = block(width: 100%, breakable: true,
  fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt,
  above: 12pt, below: 12pt)[
  #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt,
    text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]]
  #body]

// rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade
#let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint,
    stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt),
    above: 11pt, below: 11pt)[
    #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)]
    #linebreak() #body]

#let solutionbox(body) = block(above: 4pt, below: 8pt)[
  #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body]

#let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"),
  stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[
  #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))]

// Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a
// consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the
// print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a
// degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero.
#let _STD_W = 3.5
#let _WIDE_W = 5.6
#let _MAX_H = 3.4
#let _ASPECT_WIDE = 2.2
#let _UPSCALE_MAX = 1.15
#let stdfig(body) = context {
  let m = measure(body)
  let w = calc.max(m.width / 1in, 0.01)
  let h = calc.max(m.height / 1in, 0.01)
  let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W }
  let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX)
  align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body)))
}

#show figure: set block(breakable: false)
#set figure(gap: 8pt)
#show figure.caption: set text(size: 8.5pt, fill: rgb("#555"))


  
== 12.7#h(0.6em)Hamilton Cycles


  #figure(figph[A 3D model of an icosahedron.], alt: "A 3D model of an icosahedron.", caption: [The symmetries of an icosahedron, with 30 edges, 20 faces, and 12 vertices, can be analyzed using graph theory.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Describe and identify Hamilton cycles.
+ Compute the number of Hamilton cycles in a complete graph.
+ Apply and evaluate weighted graphs.


  
  In Euler Circuits and Euler Trails, we looked for circuits and paths that visited each #emph[edge] of a graph exactly once. In this section, we will look for circuits that visit each #emph[vertex] exactly once. Like many concepts in graph theory, the idea of a circuit that visits each vertex once was inspired by games and puzzles. As early as the 9th century, Indian and Islamic intellectuals wondered whether it was possible for a knight to visit every space on a chess board of a given size, which is equivalent to visiting every vertex of a graph that represents the chess board.


  In 1857, a mathematician named William Rowan Hamilton invented a puzzle in which players were asked to find a route along the edges of a dodecahedron, which visited every vertex exactly once. Let’s explore how graph theory provides insight into these games as well as practical applications such as the Traveling Salesperson Problem.


  #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((138.32pt, 90.00pt), (137.83pt, 97.46pt), stroke: 0.7pt + black)
  line((137.83pt, 97.46pt), (136.37pt, 104.79pt), stroke: 0.7pt + black)
  line((136.37pt, 104.79pt), (133.96pt, 111.87pt), stroke: 0.7pt + black)
  line((133.96pt, 111.87pt), (130.66pt, 118.58pt), stroke: 0.7pt + black)
  line((130.66pt, 118.58pt), (126.50pt, 124.80pt), stroke: 0.7pt + black)
  line((126.50pt, 124.80pt), (121.57pt, 130.42pt), stroke: 0.7pt + black)
  line((121.57pt, 130.42pt), (115.95pt, 135.35pt), stroke: 0.7pt + black)
  line((115.95pt, 135.35pt), (109.74pt, 139.50pt), stroke: 0.7pt + black)
  line((109.74pt, 139.50pt), (103.03pt, 142.81pt), stroke: 0.7pt + black)
  line((103.03pt, 142.81pt), (95.95pt, 145.21pt), stroke: 0.7pt + black)
  line((95.95pt, 145.21pt), (88.62pt, 146.67pt), stroke: 0.7pt + black)
  line((88.62pt, 146.67pt), (81.16pt, 147.16pt), stroke: 0.7pt + black)
  line((81.16pt, 147.16pt), (73.70pt, 146.67pt), stroke: 0.7pt + black)
  line((73.70pt, 146.67pt), (66.36pt, 145.21pt), stroke: 0.7pt + black)
  line((66.36pt, 145.21pt), (59.28pt, 142.81pt), stroke: 0.7pt + black)
  line((59.28pt, 142.81pt), (52.58pt, 139.50pt), stroke: 0.7pt + black)
  line((52.58pt, 139.50pt), (46.36pt, 135.35pt), stroke: 0.7pt + black)
  line((46.36pt, 135.35pt), (40.74pt, 130.42pt), stroke: 0.7pt + black)
  line((40.74pt, 130.42pt), (35.81pt, 124.80pt), stroke: 0.7pt + black)
  line((35.81pt, 124.80pt), (31.66pt, 118.58pt), stroke: 0.7pt + black)
  line((31.66pt, 118.58pt), (28.35pt, 111.87pt), stroke: 0.7pt + black)
  line((28.35pt, 111.87pt), (25.95pt, 104.79pt), stroke: 0.7pt + black)
  line((25.95pt, 104.79pt), (24.49pt, 97.46pt), stroke: 0.7pt + black)
  line((24.49pt, 97.46pt), (24.00pt, 90.00pt), stroke: 0.7pt + black)
  line((24.00pt, 90.00pt), (24.49pt, 82.54pt), stroke: 0.7pt + black)
  line((24.49pt, 82.54pt), (25.95pt, 75.21pt), stroke: 0.7pt + black)
  line((25.95pt, 75.21pt), (28.35pt, 68.13pt), stroke: 0.7pt + black)
  line((28.35pt, 68.13pt), (31.66pt, 61.42pt), stroke: 0.7pt + black)
  line((31.66pt, 61.42pt), (35.81pt, 55.20pt), stroke: 0.7pt + black)
  line((35.81pt, 55.20pt), (40.74pt, 49.58pt), stroke: 0.7pt + black)
  line((40.74pt, 49.58pt), (46.36pt, 44.65pt), stroke: 0.7pt + black)
  line((46.36pt, 44.65pt), (52.58pt, 40.50pt), stroke: 0.7pt + black)
  line((52.58pt, 40.50pt), (59.28pt, 37.19pt), stroke: 0.7pt + black)
  line((59.28pt, 37.19pt), (66.36pt, 34.79pt), stroke: 0.7pt + black)
  line((66.36pt, 34.79pt), (73.70pt, 33.33pt), stroke: 0.7pt + black)
  line((73.70pt, 33.33pt), (81.16pt, 32.84pt), stroke: 0.7pt + black)
  line((81.16pt, 32.84pt), (88.62pt, 33.33pt), stroke: 0.7pt + black)
  line((88.62pt, 33.33pt), (95.95pt, 34.79pt), stroke: 0.7pt + black)
  line((95.95pt, 34.79pt), (103.03pt, 37.19pt), stroke: 0.7pt + black)
  line((103.03pt, 37.19pt), (109.74pt, 40.50pt), stroke: 0.7pt + black)
  line((109.74pt, 40.50pt), (115.95pt, 44.65pt), stroke: 0.7pt + black)
  line((115.95pt, 44.65pt), (121.57pt, 49.58pt), stroke: 0.7pt + black)
  line((121.57pt, 49.58pt), (126.50pt, 55.20pt), stroke: 0.7pt + black)
  line((126.50pt, 55.20pt), (130.66pt, 61.42pt), stroke: 0.7pt + black)
  line((130.66pt, 61.42pt), (133.96pt, 68.13pt), stroke: 0.7pt + black)
  line((133.96pt, 68.13pt), (136.37pt, 75.21pt), stroke: 0.7pt + black)
  line((136.37pt, 75.21pt), (137.83pt, 82.54pt), stroke: 0.7pt + black)
  line((137.83pt, 82.54pt), (138.32pt, 90.00pt), stroke: 0.7pt + black)
  circle((81.16pt, 90.00pt), radius: 57.16pt, fill: rgb("#e5e7eb"), stroke: none)
  line((138.32pt, 90.00pt), (137.83pt, 97.46pt), stroke: 0.7pt + black)
  line((137.83pt, 97.46pt), (136.37pt, 104.79pt), stroke: 0.7pt + black)
  line((136.37pt, 104.79pt), (133.96pt, 111.87pt), stroke: 0.7pt + black)
  line((133.96pt, 111.87pt), (130.66pt, 118.58pt), stroke: 0.7pt + black)
  line((130.66pt, 118.58pt), (126.50pt, 124.80pt), stroke: 0.7pt + black)
  line((126.50pt, 124.80pt), (121.57pt, 130.42pt), stroke: 0.7pt + black)
  line((121.57pt, 130.42pt), (115.95pt, 135.35pt), stroke: 0.7pt + black)
  line((115.95pt, 135.35pt), (109.74pt, 139.50pt), stroke: 0.7pt + black)
  line((109.74pt, 139.50pt), (103.03pt, 142.81pt), stroke: 0.7pt + black)
  line((103.03pt, 142.81pt), (95.95pt, 145.21pt), stroke: 0.7pt + black)
  line((95.95pt, 145.21pt), (88.62pt, 146.67pt), stroke: 0.7pt + black)
  line((88.62pt, 146.67pt), (81.16pt, 147.16pt), stroke: 0.7pt + black)
  line((81.16pt, 147.16pt), (73.70pt, 146.67pt), stroke: 0.7pt + black)
  line((73.70pt, 146.67pt), (66.36pt, 145.21pt), stroke: 0.7pt + black)
  line((66.36pt, 145.21pt), (59.28pt, 142.81pt), stroke: 0.7pt + black)
  line((59.28pt, 142.81pt), (52.58pt, 139.50pt), stroke: 0.7pt + black)
  line((52.58pt, 139.50pt), (46.36pt, 135.35pt), stroke: 0.7pt + black)
  line((46.36pt, 135.35pt), (40.74pt, 130.42pt), stroke: 0.7pt + black)
  line((40.74pt, 130.42pt), (35.81pt, 124.80pt), stroke: 0.7pt + black)
  line((35.81pt, 124.80pt), (31.66pt, 118.58pt), stroke: 0.7pt + black)
  line((31.66pt, 118.58pt), (28.35pt, 111.87pt), stroke: 0.7pt + black)
  line((28.35pt, 111.87pt), (25.95pt, 104.79pt), stroke: 0.7pt + black)
  line((25.95pt, 104.79pt), (24.49pt, 97.46pt), stroke: 0.7pt + black)
  line((24.49pt, 97.46pt), (24.00pt, 90.00pt), stroke: 0.7pt + black)
  line((24.00pt, 90.00pt), (24.49pt, 82.54pt), stroke: 0.7pt + black)
  line((24.49pt, 82.54pt), (25.95pt, 75.21pt), stroke: 0.7pt + black)
  line((25.95pt, 75.21pt), (28.35pt, 68.13pt), stroke: 0.7pt + black)
  line((28.35pt, 68.13pt), (31.66pt, 61.42pt), stroke: 0.7pt + black)
  line((31.66pt, 61.42pt), (35.81pt, 55.20pt), stroke: 0.7pt + black)
  line((35.81pt, 55.20pt), (40.74pt, 49.58pt), stroke: 0.7pt + black)
  line((40.74pt, 49.58pt), (46.36pt, 44.65pt), stroke: 0.7pt + black)
  line((46.36pt, 44.65pt), (52.58pt, 40.50pt), stroke: 0.7pt + black)
  line((52.58pt, 40.50pt), (59.28pt, 37.19pt), stroke: 0.7pt + black)
  line((59.28pt, 37.19pt), (66.36pt, 34.79pt), stroke: 0.7pt + black)
  line((66.36pt, 34.79pt), (73.70pt, 33.33pt), stroke: 0.7pt + black)
  line((73.70pt, 33.33pt), (81.16pt, 32.84pt), stroke: 0.7pt + black)
  line((81.16pt, 32.84pt), (88.62pt, 33.33pt), stroke: 0.7pt + black)
  line((88.62pt, 33.33pt), (95.95pt, 34.79pt), stroke: 0.7pt + black)
  line((95.95pt, 34.79pt), (103.03pt, 37.19pt), stroke: 0.7pt + black)
  line((103.03pt, 37.19pt), (109.74pt, 40.50pt), stroke: 0.7pt + black)
  line((109.74pt, 40.50pt), (115.95pt, 44.65pt), stroke: 0.7pt + black)
  line((115.95pt, 44.65pt), (121.57pt, 49.58pt), stroke: 0.7pt + black)
  line((121.57pt, 49.58pt), (126.50pt, 55.20pt), stroke: 0.7pt + black)
  line((126.50pt, 55.20pt), (130.66pt, 61.42pt), stroke: 0.7pt + black)
  line((130.66pt, 61.42pt), (133.96pt, 68.13pt), stroke: 0.7pt + black)
  line((133.96pt, 68.13pt), (136.37pt, 75.21pt), stroke: 0.7pt + black)
  line((136.37pt, 75.21pt), (137.83pt, 82.54pt), stroke: 0.7pt + black)
  line((137.83pt, 82.54pt), (138.32pt, 90.00pt), stroke: 0.7pt + black)
  line((138.32pt, 90.00pt), (137.83pt, 94.31pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((137.83pt, 94.31pt), (136.37pt, 98.54pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((136.37pt, 98.54pt), (133.96pt, 102.63pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((133.96pt, 102.63pt), (130.66pt, 106.50pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((130.66pt, 106.50pt), (126.50pt, 110.09pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((126.50pt, 110.09pt), (121.57pt, 113.33pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((121.57pt, 113.33pt), (115.95pt, 116.18pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((115.95pt, 116.18pt), (109.74pt, 118.58pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((109.74pt, 118.58pt), (103.03pt, 120.49pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((103.03pt, 120.49pt), (95.95pt, 121.88pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((95.95pt, 121.88pt), (88.62pt, 122.72pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((88.62pt, 122.72pt), (81.16pt, 123.00pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((81.16pt, 123.00pt), (73.70pt, 122.72pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((73.70pt, 122.72pt), (66.36pt, 121.88pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((66.36pt, 121.88pt), (59.28pt, 120.49pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((59.28pt, 120.49pt), (52.58pt, 118.58pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((52.58pt, 118.58pt), (46.36pt, 116.18pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((46.36pt, 116.18pt), (40.74pt, 113.33pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((40.74pt, 113.33pt), (35.81pt, 110.09pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((35.81pt, 110.09pt), (31.66pt, 106.50pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((31.66pt, 106.50pt), (28.35pt, 102.63pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((28.35pt, 102.63pt), (25.95pt, 98.54pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((25.95pt, 98.54pt), (24.49pt, 94.31pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((24.49pt, 94.31pt), (24.00pt, 90.00pt), stroke: (paint: black, thickness: 0.6pt, dash: "dashed"))
  line((24.00pt, 90.00pt), (24.49pt, 85.69pt), stroke: 0.7pt + black)
  line((24.49pt, 85.69pt), (25.95pt, 81.46pt), stroke: 0.7pt + black)
  line((25.95pt, 81.46pt), (28.35pt, 77.37pt), stroke: 0.7pt + black)
  line((28.35pt, 77.37pt), (31.66pt, 73.50pt), stroke: 0.7pt + black)
  line((31.66pt, 73.50pt), (35.81pt, 69.91pt), stroke: 0.7pt + black)
  line((35.81pt, 69.91pt), (40.74pt, 66.67pt), stroke: 0.7pt + black)
  line((40.74pt, 66.67pt), (46.36pt, 63.82pt), stroke: 0.7pt + black)
  line((46.36pt, 63.82pt), (52.58pt, 61.42pt), stroke: 0.7pt + black)
  line((52.58pt, 61.42pt), (59.28pt, 59.51pt), stroke: 0.7pt + black)
  line((59.28pt, 59.51pt), (66.36pt, 58.12pt), stroke: 0.7pt + black)
  line((66.36pt, 58.12pt), (73.70pt, 57.28pt), stroke: 0.7pt + black)
  line((73.70pt, 57.28pt), (81.16pt, 57.00pt), stroke: 0.7pt + black)
  line((81.16pt, 57.00pt), (88.62pt, 57.28pt), stroke: 0.7pt + black)
  line((88.62pt, 57.28pt), (95.95pt, 58.12pt), stroke: 0.7pt + black)
  line((95.95pt, 58.12pt), (103.03pt, 59.51pt), stroke: 0.7pt + black)
  line((103.03pt, 59.51pt), (109.74pt, 61.42pt), stroke: 0.7pt + black)
  line((109.74pt, 61.42pt), (115.95pt, 63.82pt), stroke: 0.7pt + black)
  line((115.95pt, 63.82pt), (121.57pt, 66.67pt), stroke: 0.7pt + black)
  line((121.57pt, 66.67pt), (126.50pt, 69.91pt), stroke: 0.7pt + black)
  line((126.50pt, 69.91pt), (130.66pt, 73.50pt), stroke: 0.7pt + black)
  line((130.66pt, 73.50pt), (133.96pt, 77.37pt), stroke: 0.7pt + black)
  line((133.96pt, 77.37pt), (136.37pt, 81.46pt), stroke: 0.7pt + black)
  line((136.37pt, 81.46pt), (137.83pt, 85.69pt), stroke: 0.7pt + black)
  line((137.83pt, 85.69pt), (138.32pt, 90.00pt), stroke: 0.7pt + black)
})]),
  alt: "A 3D illustration of a truncated icosahedron, a polyhedron with pentagonal and hexagonal faces, rendered in shades of gray and blue.", caption: [A Dodecahedron],
)


  
    
=== Hamilton’s Puzzle


    Before we look at the solution to Hamilton's puzzle, let’s review some vocabulary we used in . It will be helpful to remember that directed cycle is a type of circuit that doesn’t repeat any edges or vertices.


    #figure(figph[Three concentric ovals represent directed cycles, circuits, and closed walks. The first (inner) oval labeled directed cycles (closed paths) reads, no repeated edges or vertices. The second oval labeled circuits (closed talks) reads, no repeated edges. The third oval is labeled closed walks.], alt: "Three concentric ovals represent directed cycles, circuits, and closed walks. The first (inner) oval labeled directed cycles (closed paths) reads, no repeated edges or vertices. The second oval labeled circuits (closed talks) reads, no repeated edges. The third oval is labeled closed walks.", caption: [Closed Walks, Circuits, and Directed Cycles])


    The goal of Hamilton's puzzle was to find a route along the edges of the dodecahedron, which visits each vertex exactly once. A dodecahedron is a three-dimensional space figure with faces that are all pentagons as we saw in .


    Since it is easier to visualize two dimensions rather than three, we will flatten out the dodecahedron and look at the edges and vertices on a flat surface. Graph #emph[A] in  shows a two-dimensional graph of the edges and vertices, and Graph #emph[B] shows an untangled version of Graph #emph[A] in which no edges are crossing. Graph #emph[B] in  is very similar to the design of the game board that Hamilton invented for his puzzle.


    #figure(figph[Two graphs are labeled graph A and graph B. Graph A highlights the edges of a dodecahedron. Graph B highlights the vertices of a dodecahedron.], alt: "Two graphs are labeled graph A and graph B. Graph A highlights the edges of a dodecahedron. Graph B highlights the vertices of a dodecahedron.", caption: [Graph of Edges and Vertices of Dodecahedron])


    We can see that this is a planar graph because it can be “untangled.” In order to solve Hamilton’s puzzle, we need to find a circuit that visits every vertex once. A solution is shown.


    #figure(figph[Two figures. The first figure is a 2 D view of a dodecahedron. The edges are highlighted. The second figure is a 3 D view of a dodecahedron. The edges in the front face are highlighted.], alt: "Two figures. The first figure is a 2 D view of a dodecahedron. The edges are highlighted. The second figure is a 3 D view of a dodecahedron. The edges in the front face are highlighted.", caption: [A Solution to Hamilton’s Puzzle])


    A circuit that doesn’t repeat any vertices, like the one in , is called a directed cycle. So, we can most accurately say that Hamilton’s puzzle asks us to find a directed cycle that visits every vertex in a graph exactly once. Because Hamilton created and solved this puzzle, these special circuits were named #strong[Hamilton cycles], or #strong[Hamilton circuits].


    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Icosian Game]


      When Hamilton invented his puzzle in the 19th century, it was originally called the Icosian game. This was a reference to an icosahedron, not a dodecahedron. Why? Hamilton was interested in the symmetries of icosahedrons, specifically regular icosahedrons, which have faces that are all equilateral triangles.  It turns out that this space figure has a surprising correspondence with the regular dodecahedron, a space figure with faces that are all regular pentagons. This pair of space figures have the same number of edges, while the number of faces and vertices are swapped. The icosahedron has 30 edges, 20 faces, and 12 vertices, while the dodecahedron has 30 edges, 12 faces, and 20 vertices. By relating the vertices of the dodecahedron to the faces of the icosahedron, Hamilton was able to make the mathematical connections necessary to use graph theory and dodecahedrons to make discoveries about the symmetries of icosahedrons.
]


  
  
    
=== Hamilton Cycles vs. Euler Circuits


    Let’s practice naming and identifying Hamilton cycles, as well as distinguishing them from Euler circuits. It is important to remember that Euler circuits visit all edges without repetition, while Hamilton cycles visit all vertices without repetition. Hamilton cycles are named by their vertices just like all circuits. An example is given in .


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph Z])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
  line((39.78pt, 5.86pt), (34.93pt, 7.07pt), (36.14pt, 2.22pt), fill: black, stroke: none, close: true)
  line((5.86pt, -39.78pt), (7.07pt, -34.93pt), (2.22pt, -36.14pt), fill: black, stroke: none, close: true)
  line((-39.78pt, -5.86pt), (-34.93pt, -7.07pt), (-36.14pt, -2.22pt), fill: black, stroke: none, close: true)
  line((-5.86pt, 39.78pt), (-7.07pt, 34.93pt), (-2.22pt, 36.14pt), fill: black, stroke: none, close: true)
  line((2.58pt, -36.28pt), (0.00pt, -32.00pt), (-2.58pt, -36.28pt), fill: black, stroke: none, close: true)
})]
)]),
  alt: "Two graphs. The first graph, graph Z has four vertices: a, b, c, and d. The edges connect a b, b c, c d, d a, and a c. The second graph directed edges from a to b, b to c, c to d, and d to a. A dashed line connects a to c.", caption: [Hamilton Cycle in Graph #emph[Z]],
)


    Notice that the Hamilton cycle #emph[a] → #emph[b] → #emph[c] → #emph[d] for Graph #emph[Z] in  is NOT an Euler circuit, because it does not visit edge #math.equation(block: false, alt: "ac")[$italic("ac")$]. Some Hamilton cycles are also Euler circuits while some are not, and some Euler circuits are Hamilton cycles while some are not.


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[TIP! Sometimes students confuse Euler circuits with Hamilton cycles. To help you remember, think of the E in Euler as standing for Edge.]
]


    #examplebox("Example 1")[Differentiating between Hamilton Cycles or Euler Circuits][
Use  to determine whether the given circuit is a Hamilton cycle, an Euler circuit, both, or neither.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph Q])
  line((0.00pt, 42.00pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, 29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[c])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[h])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[f])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[b])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[g])
})]),
  alt: "Graph Q has two overlapping quadrilaterals. The vertices of the outer quadrilateral are a, c, h, and f. The vertices of the inner quadrilateral are d, b, e, and g. The vertex, d rests on the edge a f. The vertex, b rests on the edge a c. The vertex, e rests on the edge c h. The vertex, g rests on the edge hf.", caption: [Graph #emph[Q]],
)


        + #emph[a] → #emph[b] → #emph[c] → #emph[e] → #emph[h] → #emph[g] → #emph[f] → #emph[d] → #emph[a]
+ #emph[g] → #emph[e] → #emph[h] → #emph[g] → #emph[f] → #emph[d] → #emph[a] → #emph[b] → #emph[d] → #emph[g]
+ #emph[a] → #emph[b] → #emph[c] → #emph[e] → #emph[h] → #emph[g] → #emph[f] → #emph[d] → #emph[b] → #emph[e] → #emph[g] → #emph[d] → #emph[a]


      
      #solutionbox[
+ This circuit is a Hamilton cycle only. It visits each vertex exactly once, so, it is a Hamilton cycle. It is not an Euler circuit because it doesn’t visit all of the edges.
+ This circuit is neither Hamilton cycle nor an Euler circuit. It doesn’t visit vertex #math.equation(block: false, alt: "c")[$c$], so, it is not a Hamilton cycle. It also doesn’t visit edges #math.equation(block: false, alt: "be")[$italic("be")$] and #math.equation(block: false, alt: "ce")[$italic("ce")$], so, it is not an Euler circuit.
+ This circuit is an Euler circuit only. It visits several vertices more than once; so, it is not a Hamilton cycle. It visits every edge exactly once, so, it is an Euler circuit.
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[TIP! Euler circuits never skip a vertex, so, they only fail to be Hamilton cycles when they visit a vertex more than once. Hamilton cycles never visit any edges twice, so, they only fail to be Euler circuits when they skip edges.]
]


    
    Notice that the graph is a cycle. A cycle will always be Eulerian because all vertices are degree 2. Moreover, any circuit in the graph will always be both an Euler circuit and a Hamilton cycle. It is not always as easy to determine if a graph has a Hamilton cycle as it is to see that it has an Euler circuit, but there is a large group of graphs that we know will always have Hamilton cycles, the complete graphs. Since all vertices in a complete graph are adjacent, we can always find a directed cycle that visits all the vertices. For example, look at the directed six-cycle, #emph[n] → #emph[o] → #emph[p] → #emph[q] → #emph[r] → #emph[s], in the complete graph with six vertices in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[o])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[p])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[q])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[r])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[s])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[n])
  line((32.71pt, 26.09pt), (27.71pt, 26.00pt), (30.13pt, 21.63pt), fill: black, stroke: none, close: true)
  line((38.95pt, -15.28pt), (36.37pt, -11.00pt), (33.80pt, -15.28pt), fill: black, stroke: none, close: true)
  line((6.24pt, -41.37pt), (8.66pt, -37.00pt), (3.66pt, -36.91pt), fill: black, stroke: none, close: true)
  line((-32.71pt, -26.09pt), (-27.71pt, -26.00pt), (-30.13pt, -21.63pt), fill: black, stroke: none, close: true)
  line((-38.95pt, 15.28pt), (-36.37pt, 11.00pt), (-33.80pt, 15.28pt), fill: black, stroke: none, close: true)
  line((-6.24pt, 41.37pt), (-8.66pt, 37.00pt), (-3.66pt, 36.91pt), fill: black, stroke: none, close: true)
})]),
  alt: "A directed graph has six vertices: o, p, q, r, s, and n. All the vertices are interconnected. Directed arrows flow from o to p, p to q, q to r, r to s, s to n, and n to o.", caption: [Directed Cycle in Complete Graph],
)


    That is not the only directed six-cycle in the graph though. We could find another just be reversing the direction, and we could find even more by using different edges. So, how many Hamilton cycles are in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices? Before we tackle this problem, let’s look at a shorthand notation that we use in mathematics which will be helpful to us.


  
  
    
=== Factorials


    In many areas of mathematics, we must calculate products like #math.equation(block: false, alt: "7 times 6 times 5 times 4 times 3 times 2 times 1")[$7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1$] or #math.equation(block: false, alt: "11 times 10 times 9 times 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1")[$11 ⋅ 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1$], products that involve multiplying all the counting numbers from a particular number down to 1. Imagine that the product happened to be all the numbers from 100 down to 1. That’s a lot of writing! Instead of writing all of that out, mathematicians came up with a shorthand notation. For example, instead of #math.equation(block: false, alt: "7 times 6 times 5 times 4 times 3 times 2 times 1")[$7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1$], we write #math.equation(block: false, alt: "7 !")[$7 !$], which is read “7 #strong[factorial].” In other words, the product of all the counting numbers from #math.equation(block: false, alt: "n")[$n$] down to 1 is called #math.equation(block: false, alt: "n")[$n$] factorial and it is written #math.equation(block: false, alt: "n !")[$n !$]


    #examplebox("Example 2")[Evaluating Factorials][
Evaluate #math.equation(block: false, alt: "n !")[$n !$] and #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$] for #math.equation(block: false, alt: "n equals 4")[$n = 4$].


      
      #solutionbox[
#math.equation(block: false, alt: "n ! equals 4 ! equals 4 times 3 times 2 times 1 equals 24")[$n ! = 4 ! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24$] and #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis ! equals open parenthesis 4 minus 1 close parenthesis ! equals 3 ! equals 3 times 2 times 1 equals 6")[$( n − 1 ) ! = ( 4 − 1 ) ! = 3 ! = 3 ⋅ 2 ⋅ 1 = 6$]
]
]


    
    A common use for factorials is counting the number of ways to arrange objects. Suppose that there were three students, Aryana, Byron, and Carlos, who wanted to line up in a row. How many arrangements are possible? There are six possibilities: ABC, ACB, BAC, BCA, CAB, or CBA. Notice that there were three students being arranged, and the number of possible arrangements is three.


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
The number of ways to arrange #math.equation(block: false, alt: "n")[$n$] distinct objects is #math.equation(block: false, alt: "n !")[$n !$].
]


    #examplebox("Example 3")[Counting Arrangements of Letters][
Find the number of ways to arrange the letters a, b, c, and d.


      
      #solutionbox[
#math.equation(block: true, alt: "4 ! equals 4 times 3 times 2 times 1 equals 24")[$4 ! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24$]
]
]


    
  
  
    
=== Counting Hamilton Cycles in Complete Graphs


    Now, let’s get back to answering the question of how many Hamilton cycles are in a complete graph. In , we have drawn all the four cycles in a complete graph with four vertices. Remember, cycles can be named starting with any vertex in the cycle, but we will name them starting with vertex #math.equation(block: false, alt: "a")[$a$].


    #figure(table(
  columns: 4, align: left, inset: 6pt,
  table.header([Complete Graph], [Cycle], [Cycle], [Cycle]),
  [], [], [], [],
  [#strong[Cycle Name Clockwise]], [#emph[(a, b, c, d)]], [#emph[(a, b, d, c)]], [#emph[(a, c, b, d)]],
  [#strong[Cycle Name Counterclockwise]], [#emph[(a, d, c, b)]], [#emph[(a, c, d, b)]], [#emph[(a, d, b, c)]],
))


    shows that there are three unique four-cycles in a complete graph with four vertices. Notice that there were two ways to name each cycle, one reading the vertices in a clockwise direction and one reading the vertices in a counterclockwise direction. This is important to us because we are interested in Hamilton cycles, which are #emph[directed] cycles. Although the cycles #emph[(a, b, c, d)] and #emph[(a, d, c, b)] are the same cycle, the directed cycles, #emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[a] and #emph[a] → #emph[d] → #emph[c] → #emph[b] → #emph[a], which travel the same route in reverse order are considered different directed cycles, as shown.


    #figure(table(
  columns: 4, align: left, inset: 6pt,
  table.header([Complete Graph], [Cycle], [Cycle], [Cycle]),
  [], [], [], [],
  [#strong[Clockwise Hamilton Cycle]], [#emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[a]], [#emph[a] → #emph[b] → #emph[d] → #emph[c] → #emph[a]], [#emph[a] → #emph[c] → #emph[b] → #emph[d] → #emph[a]],
  [#strong[Counter-clockwise Hamilton Cycle]], [#emph[a] → #emph[d] → #emph[c] → #emph[b] → #emph[a]], [#emph[a] → #emph[c] → #emph[d] → #emph[b] → #emph[a]], [#emph[a] → #emph[d] → #emph[b] → #emph[c] → #emph[a]],
))


    The six directed four-cycles in  are the only distinct Hamilton cycles in a complete graph with four vertices. Six is also the number of ways to arrange the three letters b, c, and d. (Do you see why?) The number of ways to arrange three letters is #math.equation(block: false, alt: "3 ! equals 3 times 2 times 1 equals 6")[$3 ! = 3 ⋅ 2 ⋅ 1 = 6$]. Similarly, the number of Hamilton cycles in a graph with five vertices is the number of ways to arrange four letters, which is #math.equation(block: false, alt: "4 ! equals 4 times 3 times 2 times 1 equals 24")[$4 ! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24$]. In general, to find the number of Hamilton cycles in a graph, we take one less than the number of vertices and find its factorial.


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
The number of distinct Hamilton cycles in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$]
]


    #examplebox("Example 4")[Counting Hamilton Cycles in a Complete Graph][
How many Hamilton cycles are in the complete graph in ?


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph L])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[m])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[n])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[o])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[p])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[q])
})]),
  alt: "Graph L has five vertices: m, n, o, p, and q. All vertices are interconnected.", caption: [Complete Graph #emph[L]],
)


      
      #solutionbox[
There are five vertices in the graph. Using #math.equation(block: false, alt: "n equals 5")[$n = 5$], we have#math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis ! equals open parenthesis 5 minus 1 close parenthesis ! equals 4 ! equals 4 times 3 times 2 times 1 equals 24")[$( n − 1 ) ! = ( 5 − 1 ) ! = 4 ! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24$] Hamilton cycles.
]
]


    
  
  
    
=== Weighted Graphs


    Suppose that an officer in the U.S. Air Force who is stationed at Vandenberg Air Force base must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needs to visit each base once. The vertices in the graph in  represent the four U.S. Air Force bases, Vandenberg, Edwards, Los Angeles, and Beale. The edges are labeled to with the driving distance between each pair of cities.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  content((21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410])
  content((21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396])
  content((-21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159])
  content((-21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106])
  content((-18.48pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439])
  content((0.00pt, 10.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[E])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[L])
})]),
  alt: "A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.", caption: [Graph of Four California Air Force Bases],
)


    The graph in  is called a #strong[weighted graph], because each edge has been assigned a value or weight. The weights can represent quantities such as time, distance, money, or any quantity associated with the adjacent vertices joined by the edges. The #strong[total weight] of any walk, trail, or path is the sum of the weights of the edges it visits.


    Notice that the officer’s trip can be represented as a Hamilton cycle, because each of the four vertices in the graph is visited exactly once.


    #examplebox("Example 5")[Finding Hamilton Cycles of Lowest Weight][
Use  and the given Hamilton cycles to answer the following questions.


        #emph[V] → #emph[L] → #emph[E] → #emph[B] → #emph[V]


        #emph[V] → #emph[L] → #emph[B] → #emph[E] → #emph[V]


        #emph[V] → #emph[E] → #emph[L] → #emph[B] → #emph[V]


        #emph[V] → #emph[B] → #emph[E] → #emph[L] → #emph[V]


        + Which of the Hamilton cycles (directed cycles) lie on the same cycle (undirected cycle) in the graph?
+ Find the total weight of each cycle.
+ Of the four, which of the Hamilton cycles describes the shortest trip for the officer? Describe the route.


      
      #solutionbox[
+ #emph[V] → #emph[L] → #emph[E] → #emph[B] → #emph[V] and #emph[V] → #emph[B] → #emph[E] → #emph[L] → #emph[V] follow the same edges in reverse order.
+ Any Hamilton cycles that lie on the same cycle will have the same edges and the same total weight.
    #emph[V] → #emph[L] → #emph[E] → #emph[B] → #emph[V] and #emph[V] → #emph[B] → #emph[E] → #emph[L] → #emph[V] each have total weight #math.equation(block: false, alt: "159 plus 106 plus 410 plus 396 equals 1071")[$159 + 106 + 410 + 396 = 1071$].

#emph[V] → #emph[L] → #emph[B] → #emph[E] → #emph[V] has a total weight #math.equation(block: false, alt: "159 plus 439 plus 410 plus 207 equals 1215")[$159 + 439 + 410 + 207 = 1215$].

#emph[V] → #emph[E] → #emph[L] → #emph[B] → #emph[V] has a total weight #math.equation(block: false, alt: "396 plus 439 plus 106 plus 207 equals 1148")[$396 + 439 + 106 + 207 = 1148$].
+ Hamilton cycles #emph[V] → #emph[L] → #emph[E] → #emph[B] → #emph[V] and #emph[V] → #emph[B] → #emph[E] → #emph[L] → #emph[V] each have the lowest total weight. The officer would take the route from Vandenberg, to Los Angeles, to Edwards, to Beale, and back to Vandenberg, or reverse that route.
]
]


    
  
  
  
  
    
=== Key Terms


    - Hamilton cycle, or Hamilton circuit
- #math.equation(block: false, alt: "n")[$n$] factorial
- weighted graph
- total weight


  
  
    
=== Key Concepts


    - A Hamilton cycle is a directed cycle, or circuit, that visits each vertex exactly once.
- Some Hamilton cycles are also Euler circuits, but some are not.
- Hamilton cycles that follow the same undirected cycle in the same direction are considered the same cycle even if they begin at a different vertex.
- The number of unique Hamilton cycles in a complete graph with n vertices is the same as the number of ways to arrange #math.equation(block: false, alt: "n minus 1")[$n − 1$] distinct objects.
- Weighted graphs have a value assigned to each edge, which can represent distance, time, money and other quantities.


  
  
    
=== Formulas


    The number of ways to arrange #math.equation(block: false, alt: "n")[$n$] distinct objects is #math.equation(block: false, alt: "n !")[$n !$].


    The number of distinct Hamilton cycles in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$].