#set document(title: "12.4 Navigating Graphs", 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.4#h(0.6em)Navigating Graphs


  #figure(figph[People walking through a maze of hedges.], alt: "People walking through a maze of hedges.", caption: [Visitors navigate a garden maze.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Describe and identify walks, trails, paths, and circuits.
+ Solve application problems using walks, trails, paths, and circuits.
+ Identify the chromatic number of a graph.
+ Describe the Four-Color Problem.
+ Solve applications using graph colorings.


  
  Now that we know the basic parts of graphs and we can distinguish one graph from another, it is time to really put our graphs to work for us. Many applications of graph theory involve navigating through a graph very much like you would navigate through a maze. Imagine that you are at the entrance to a maze. Your goal is to get from one point to another as efficiently as possible. Maybe there are treasures hidden along the way that make straying from the shortest path worthwhile, or maybe you just need to get to the end fast. Either way, you definitely want to avoid any wrong turns that would cause unnecessary backtracking. Luckily, graph theory is here to help!


  
    
=== Walks


    Suppose  is a maze you want to solve. You want to get from the start to the end.


    #figure(figph[A maze with its start and end labeled.], alt: "A maze with its start and end labeled.", caption: [Your Maze])


    You can approach this task any way you want. The only rule is that you can’t climb over the wall. To put this in the context of graph theory, let’s imagine that at every intersection and every turn, there is a vertex. The edges that join the vertices must stay within the walls. The graph within the maze would look like .


    #figure(figph[A maze with its start and end labeled. Vertices are marked at each corner of the maze. A path connects all the vertices of the maze.], alt: "A maze with its start and end labeled. Vertices are marked at each corner of the maze. A path connects all the vertices of the maze.", caption: [The Graph in Your Maze])


    One approach to solving a maze is to just start walking. It is not the most efficient approach. You might cross through the same intersection twice. You might backtrack a bit. It’s okay. We are just out for a walk. It might look something like the black sequence of vertices and edges in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((0.00pt, 49.00pt), anchor: "south", text(size: 9pt)[start])
  circle((0.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[end])
})]),
  alt: "A maze with its start and end labeled. Vertices are marked at each corner of the maze. A path connects all the vertices of the maze. The path from start to end is highlighted.", caption: [The Walk Through the Graph in Your Maze],
)


    This type of sequence of adjacent vertices and edges is actually called a #strong[walk] (or #strong[directed walk]) in graph theory too!


    A walk can be identified by naming the sequence of its vertices (or by naming the sequence of its edges if those are labeled). Let’s take the graph out of the context of the maze and give each vertex a name and each edge of the walk a direction as in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((40.52pt, 118.03pt), (0.00pt, 124.79pt), stroke: 0.7pt + black)
  line((0.00pt, 124.79pt), (-40.52pt, 118.03pt), stroke: 0.7pt + black)
  line((-40.52pt, 118.03pt), (-76.65pt, 98.48pt), stroke: 0.7pt + black)
  line((76.65pt, 98.48pt), (-76.65pt, 98.48pt), stroke: 0.7pt + black)
  line((76.65pt, 98.48pt), (104.47pt, 68.25pt), stroke: 0.7pt + black)
  line((104.47pt, 68.25pt), (120.97pt, 30.63pt), stroke: 0.7pt + black)
  line((114.28pt, -50.13pt), (59.39pt, -109.75pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((124.37pt, -10.31pt), (91.81pt, -84.52pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-120.97pt, 30.63pt), (-104.47pt, 68.25pt), stroke: 0.7pt + black)
  line((-120.97pt, 30.63pt), (-91.81pt, -84.52pt), stroke: 0.7pt + black)
  line((-124.37pt, -10.31pt), (-114.28pt, -50.13pt), stroke: 0.7pt + black)
  line((-59.39pt, -109.75pt), (-91.81pt, -84.52pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-91.81pt, -84.52pt), (-114.28pt, -50.13pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-59.39pt, -109.75pt), (-20.54pt, -123.09pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-20.54pt, -123.09pt), (20.54pt, -123.09pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((20.54pt, -123.09pt), (91.81pt, -84.52pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-114.28pt, -50.13pt), (59.39pt, -109.75pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 124.79pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 124.79pt), text(size: 9pt, fill: black)[a])
  circle((40.52pt, 118.03pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.52pt, 118.03pt), text(size: 9pt, fill: black)[l])
  circle((76.65pt, 98.48pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((76.65pt, 98.48pt), text(size: 9pt, fill: black)[e])
  circle((104.47pt, 68.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((104.47pt, 68.25pt), text(size: 9pt, fill: black)[h])
  circle((120.97pt, 30.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((120.97pt, 30.63pt), text(size: 9pt, fill: black)[m])
  circle((124.37pt, -10.31pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((140.58pt, -11.38pt), anchor: "west", text(size: 9pt)[start])
  circle((114.28pt, -50.13pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((114.28pt, -50.13pt), text(size: 9pt, fill: black)[r])
  circle((91.81pt, -84.52pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((91.81pt, -84.52pt), text(size: 9pt, fill: black)[end])
  circle((59.39pt, -109.75pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((59.39pt, -109.75pt), text(size: 9pt, fill: black)[s])
  circle((20.54pt, -123.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((20.54pt, -123.09pt), text(size: 9pt, fill: black)[o])
  circle((-20.54pt, -123.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-20.54pt, -123.09pt), text(size: 9pt, fill: black)[n])
  circle((-59.39pt, -109.75pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-59.39pt, -109.75pt), text(size: 9pt, fill: black)[i])
  circle((-91.81pt, -84.52pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-91.81pt, -84.52pt), text(size: 9pt, fill: black)[j])
  circle((-114.28pt, -50.13pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-114.28pt, -50.13pt), text(size: 9pt, fill: black)[k])
  circle((-124.37pt, -10.31pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-124.37pt, -10.31pt), text(size: 9pt, fill: black)[g])
  circle((-120.97pt, 30.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-120.97pt, 30.63pt), text(size: 9pt, fill: black)[c])
  circle((-104.47pt, 68.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-104.47pt, 68.25pt), text(size: 9pt, fill: black)[d])
  circle((-76.65pt, 98.48pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-76.65pt, 98.48pt), text(size: 9pt, fill: black)[f])
  circle((-40.52pt, 118.03pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.52pt, 118.03pt), text(size: 9pt, fill: black)[b])
  line((-107.12pt, 68.63pt), (-106.48pt, 63.68pt), (-102.40pt, 66.56pt), fill: black, stroke: none, close: true)
  line((-89.49pt, -83.19pt), (-93.04pt, -79.67pt), (-94.49pt, -84.46pt), fill: black, stroke: none, close: true)
})]),
  alt: "A graph with 19 vertices and 19 edges. The vertices are a, l, e, h, m, p, r, q, s, o, n, i, j, k, g, c, d, f, and b. The edges connect l a, a b, b f, e f, e h, h m, r s, p q, c d c j, g k, i j, j k, i n, n o, o q, and k s. The following path is highlighted p, q, o, n, i, j, k, s, and r. p is labeled start and q is labeled end. The edges from j to c and c to d are connected via double-headed arrows.", caption: [The Graph without Your Maze],
)


    The name of this walk from #emph[p] to #emph[r] is #emph[p] → #emph[q] → #emph[o] → #emph[n] → #emph[i] → #emph[j] → #emph[c] → #emph[d] → #emph[c] → #emph[j] → #emph[k] → #emph[s] → #emph[r]. When a particular edge on our graph was traveled in both directions, it had arrows in both directions and the letters of vertices that were visited more than once had to be repeated in the name of the walk.


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[Not every list of vertices or list of edges makes a path. The order must take into account the way in which the edges and vertices are connected. The list must be a sequence, which means they are in order. No edges or vertices can be skipped and you cannot go off the graph.]
]


    #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 X])
  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((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  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((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  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((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph Y])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((40.95pt, -9.35pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-40.95pt, -9.35pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-40.95pt, -9.35pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (18.22pt, -37.84pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  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((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[b])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[c])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[d])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[e])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[f])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[g])
})]
)]),
  alt: "Two graphs are labeled graph X and graph Y. Graph X has six vertices: a, b, c, d, e, and f. The vertices a, b, and e are connected by three edges and it resembles a triangle. The vertices, c, d, and f are connected by three edges and it resembles a triangle. These two triangles overlap and the point where they overlap has no vertex. The edges from b to d and d to f are highlighted. Graph Y is the same as that of graph X. The point where they overlap has a vertex, g.", caption: [A Walk or Not a Walk?],
)


    The highlighted edges Graph #emph[Y] in  represent a walk between #emph[f] and #emph[b]. The highlighted edges in Graph #emph[X] do #emph[not] represent a walk between #emph[f] and #emph[b], because there is a turn at a point that is not a vertex. This is like climbing over a wall when you are walking through a maze. Another way of saying this is that #emph[b] → #emph[d] → #emph[f] is not a walk, because there is no edge between #emph[b] and #emph[d].


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[A point on a graph where two edges cross is not a vertex.]
]


    #examplebox("Example 1")[Naming a Walk Through A House][
shows the floor plan of a house. Use the floor plan to answer each question.


        #figure(figph[A floor plan of a house includes the master bedroom, bedroom, kitchen, living room, hallway, garage, and restroom.], alt: "A floor plan of a house includes the master bedroom, bedroom, kitchen, living room, hallway, garage, and restroom.", caption: [Floor Plan of a House])


        + Draw a graph to represent the floor plan in which each vertex represents a different room (or hallway) and edges represent doorways between rooms.
+ Name a walk through the house that begins in the living room, ends in the garage and visits each room (or hallway) at least once.


      
      #solutionbox[
+ #strong[Step 1:] We will need a vertex for each room and it is convenient to label them according to the names of the rooms. Visualize the scenario in your head as shown. You don’t have to write this step on your paper.

#figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-18.22pt, -37.84pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-32.84pt, 26.19pt), 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((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[B])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[K])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[L])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[H])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[G])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[R])
  line((-3.78pt, 37.00pt), (-2.23pt, 32.25pt), (1.24pt, 35.85pt), fill: black, stroke: none, close: true)
  line((27.26pt, 23.33pt), (26.60pt, 18.37pt), (31.29pt, 20.11pt), fill: black, stroke: none, close: true)
  line((12.51pt, -35.26pt), (8.22pt, -37.84pt), (12.51pt, -40.42pt), fill: black, stroke: none, close: true)
  line((-39.40pt, -15.42pt), (-34.71pt, -17.16pt), (-35.37pt, -12.21pt), fill: black, stroke: none, close: true)
  line((35.37pt, -12.21pt), (34.71pt, -17.16pt), (39.40pt, -15.42pt), fill: black, stroke: none, close: true)
  line((-31.29pt, 20.11pt), (-26.60pt, 18.37pt), (-27.26pt, 23.33pt), fill: black, stroke: none, close: true)
})]),
  alt: "A floor plan of a house includes the master bedroom, bedroom, kitchen, living room, hallway, garage, and restroom. The following vertices are assigned to rooms: master bedroom, M; bedroom, B; kitchen, K; living room, L; hallway, H; garage, G; and restroom, R. Edges from H lead to M, B, L, and G. Edges from L lead to K and R.", caption: [Assigning Vertices to Rooms],
)

#strong[Step 2:] Draw a graph to represent the scenario. Start with the vertices. Then connect those vertices that share a doorway in the floorplan as shown.

#figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((18.22pt, -37.84pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-18.22pt, -37.84pt), 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((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[B])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[K])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[H])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[L])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[G])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[R])
})]),
  alt: "A graph of the floor plan. The graph has seven vertices: M, B, K, H, L, G, and R. Edges from H lead to M, B, and G. Edges from L lead to K and R. An edge connects H with L.", caption: [Graph of the Floor plan],
)
+ #strong[Step 1:] Draw a path that begins at vertex #emph[L], representing the living room, and ending at vertex #emph[G], representing the garage making sure to visit every room at least once. There are many ways this can be done. You may want to number the edges to keep track of their order. One example is shown.

#figure(figph[A graph of the floor plan. The graph has seven vertices: M, B, K, H, L, G, and R. Edge 1: L to R. Edge 2: R to L. Edge 3: L to K. Edge 4: K to L. Edge 5: L to H. Edge 6: H to B. Edge 7: B to H. Edge 8: H to M. Edge 9: M to H. Edge 10: H to G.], alt: "A graph of the floor plan. The graph has seven vertices: M, B, K, H, L, G, and R. Edge 1: L to R. Edge 2: R to L. Edge 3: L to K. Edge 4: K to L. Edge 5: L to H. Edge 6: H to B. Edge 7: B to H. Edge 8: H to M. Edge 9: M to H. Edge 10: H to G.", caption: [Draw the Path from #emph[L] to #emph[G]])

#strong[Step 2:] Name the path that you followed by listing the vertices in the order you visited them.

#emph[L] → #emph[R] → #emph[L] → #emph[K] → #emph[L] → #emph[H] → #emph[B] → #emph[H] → #emph[M] → #emph[H] → #emph[G]
]
]


    
  
  
    
=== Paths and Trails


    A walk is the most basic way of navigating a graph because it has no restrictions except staying on the graph. When there are restrictions on which vertices or edges we can visit, we will call the walk by a different name. For example, if we want to find a walk that avoids travelling the same edge twice, we will say we want to find a #strong[trail] (or #strong[directed trail]). If we want to find a walk that avoids visiting the same vertex twice, we will say, we want to find a #strong[path] (or #strong[directed path]).


    Walks, trails, and paths are all related.


    + All paths are trails, but trails that visit the same vertex twice are not paths.
+ All trails are walks, but walks in which an edge is visited twice would not be trails.


    We can visualize the relationship as in .


    #figure(
  stdfig([_(no graphs in spec)_]),
  alt: "Three concentric ovals represent paths, trails, and walks. The first (inner) oval labeled paths reads, no repeated edges or vertices. The second oval labeled trails reads, no repeated edges. The third oval is labeled walks.", caption: [Walks, Trails, and Paths],
)


    Let’s practice identifying walks, trails, and paths using the graphs 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)[A])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-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((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)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[c])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[d])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[e])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[f])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[K])
  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), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.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: "Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. The edges connect m n, n o, n q, q o, o p, n p, and m p.", caption: [Graphs #emph[A] and #emph[K]],
)


    #examplebox("Example 2")[Identifying Walks, Paths, and Trails][
Consider each sequence of vertices from Graph #emph[A] in . Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.


        + #emph[b] → #emph[c] → #emph[d] → #emph[e] → #emph[f]
+ #emph[c] → #emph[b] → #emph[d] → #emph[b] → #emph[e]
+ #emph[c] → #emph[f] → #emph[e] → #emph[d] → #emph[b] → #emph[c]
+ #emph[b] → #emph[e] → #emph[f] → #emph[c] → #emph[b] → #emph[d]


      
      #solutionbox[
+ First, check to see if the sequence of vertices is a walk by making sure that the vertices are consecutive. As you can see in , there is no edge between vertex #emph[c] and vertex #emph[d].
    #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 A])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-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((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((39.94pt, 12.98pt), (24.69pt, -33.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)[b])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[c])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[d])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[e])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[f])
  line((36.84pt, 18.42pt), (31.85pt, 18.86pt), (33.81pt, 14.25pt), fill: black, stroke: none, close: true)
  line((-18.97pt, -36.56pt), (-14.69pt, -33.98pt), (-18.97pt, -31.40pt), fill: black, stroke: none, close: true)
  line((-40.63pt, 6.75pt), (-36.85pt, 3.47pt), (-35.73pt, 8.34pt), fill: black, stroke: none, close: true)
  line((28.90pt, -29.34pt), (27.78pt, -24.47pt), (24.00pt, -27.75pt), fill: black, stroke: none, close: true)
})]),
  alt: "Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. A sequence of arrows flows from b to c, c to d, d to e, and e to f.", caption: none,
)

This means that the sequence is not a walk. If it is not a walk, then it can’t be a path and it cannot be a trail, so, it is none of these.
+ First, check to see if the sequence is a walk. As you can see in , the vertices are consecutive.
    #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 A])
  bezier((0.00pt, 42.00pt), (39.94pt, 12.98pt), (17.50pt, 24.09pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-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((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)
  bezier((39.94pt, 12.98pt), (0.00pt, 42.00pt), (17.50pt, 24.09pt), stroke: 0.7pt + black)
  content((15.31pt, -5.11pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[2])
  content((-15.31pt, -5.11pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[4])
  content((0.00pt, -33.98pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[3])
  content((23.60pt, 22.41pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[1])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[c])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[d])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[e])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[f])
  line((25.37pt, -27.75pt), (21.60pt, -24.47pt), (20.47pt, -29.34pt), fill: black, stroke: none, close: true)
  line((-20.47pt, -29.34pt), (-21.60pt, -24.47pt), (-25.37pt, -27.75pt), fill: black, stroke: none, close: true)
  line((-18.97pt, -36.56pt), (-14.69pt, -33.98pt), (-18.97pt, -31.40pt), fill: black, stroke: none, close: true)
  line((-4.84pt, 43.26pt), (0.00pt, 42.00pt), (-1.15pt, 46.87pt), fill: black, stroke: none, close: true)
})]),
  alt: "Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. An arrow labeled 1 flows from c to b. An arrow labeled 2 flows from b to d. An arrow labeled 3 flows from d to e. An arrow labeled 4 flows from b to e.", caption: none,
)

This means that the sequence is a walk. Since the vertex #emph[b] is visited twice, this walk is not a path. Since edge #math.equation(block: false, alt: "bd")[$italic("bd")$] is traveled twice, this walk is not a trail. So, the sequence is only a walk.
+ First, check to see if the sequence is a walk. We can see in  that the vertices are consecutive, which means it is a walk.
    #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 A])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  content((19.97pt, 27.49pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[5])
  content((9.59pt, 12.98pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[1])
  content((15.31pt, -5.11pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[4])
  content((0.00pt, -33.98pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[3])
  content((-32.32pt, -10.50pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[2])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[c])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[d])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[e])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[f])
  line((36.84pt, 18.42pt), (31.85pt, 18.86pt), (33.81pt, 14.25pt), fill: black, stroke: none, close: true)
  line((-34.23pt, 10.40pt), (-29.94pt, 12.98pt), (-34.23pt, 15.56pt), fill: black, stroke: none, close: true)
  line((-0.69pt, 35.77pt), (3.09pt, 32.49pt), (4.22pt, 37.36pt), fill: black, stroke: none, close: true)
  line((18.97pt, -31.40pt), (14.69pt, -33.98pt), (18.97pt, -36.56pt), fill: black, stroke: none, close: true)
  line((-24.00pt, -27.75pt), (-27.78pt, -24.47pt), (-28.90pt, -29.34pt), fill: black, stroke: none, close: true)
})]),
  alt: "Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. An arrow labeled 1 flows from c to f. An arrow labeled 2 flows from f to e. An arrow labeled 3 flows from e to d. An arrow labeled 4 flows from d to b. An arrow labeled 5 flows from b to c.", caption: none,
)

Next, check to see if any vertex is visited twice. Remember, we do #emph[not] consider beginning and ending at the same vertex to be visiting a vertex twice. So, no vertex was visited twice. This means we have a walk that is also a path. Next check to see if any edge was visited twice; none were. So, the sequence is a walk, a path, and a trail.
+ First, check to see if the sequence is a walk. We can see in  that the vertices are consecutive, which means it is a walk.
    #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 A])
  bezier((0.00pt, 42.00pt), (39.94pt, 12.98pt), (17.50pt, 24.09pt), stroke: 0.7pt + black)
  bezier((39.94pt, 12.98pt), (-39.94pt, 12.98pt), (-0.00pt, 17.18pt), 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((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)
  bezier((-39.94pt, 12.98pt), (39.94pt, 12.98pt), (-0.00pt, 17.18pt), stroke: 0.7pt + black)
  bezier((39.94pt, 12.98pt), (0.00pt, 42.00pt), (17.50pt, 24.09pt), stroke: 0.7pt + black)
  content((12.34pt, 4.01pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[5])
  content((-12.34pt, 4.01pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[1])
  content((-32.32pt, -10.50pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[2])
  content((-0.00pt, 15.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[3])
  content((18.74pt, 25.79pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[4])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[c])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[d])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[e])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[f])
  line((25.37pt, -27.75pt), (21.60pt, -24.47pt), (20.47pt, -29.34pt), fill: black, stroke: none, close: true)
  line((-20.47pt, -29.34pt), (-21.60pt, -24.47pt), (-25.37pt, -27.75pt), fill: black, stroke: none, close: true)
  line((-40.63pt, 6.75pt), (-36.85pt, 3.47pt), (-35.73pt, 8.34pt), fill: black, stroke: none, close: true)
  line((44.47pt, 15.09pt), (39.94pt, 12.98pt), (43.94pt, 9.97pt), fill: black, stroke: none, close: true)
  line((-4.84pt, 43.26pt), (0.00pt, 42.00pt), (-1.15pt, 46.87pt), fill: black, stroke: none, close: true)
})]),
  alt: "Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. An arrow labeled 1 flows from b to e. An arrow labeled 2 flows from e to f. An arrow labeled 3 flows from f to c. An arrow labeled 4 flows from c to b. An arrow labeled 5 flows from b to d.", caption: none,
)

Next check to see if any vertex is visited twice. Since vertex #emph[b] is visited twice, this is not a path. Finally, check to see if any edges are traveled twice. Since no edges are traveled twice, this is a trail. So, the sequence of vertices is a walk and a trail.
]
]


    
    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/walks_trails_paths")[Walks, Trails, and Paths in Graph Theory]
]


  
  
    
=== Circuits


    In many applications of graph theory, such as creating efficient delivery routes, beginning and ending at the same location is a requirement. When a walk, path, or trail end at the same location or vertex they began, we call it #strong[closed]. Otherwise, we call it #strong[open] (does not begin and end at the same location or vertex). Some examples of closed walks, closed trails, and closed paths are given in in the following table.


    #figure(table(
  columns: 3, align: left, inset: 6pt,
  table.header([DESCRIPTION], [EXAMPLE], [CHARACTERISTICS]),
  [A closed walk is a walk that begins and ends at the same vertex.], [#emph[d] → #emph[f] → #emph[b] → #emph[c] → #emph[f] → #emph[d]], [Alternating sequence of vertices and edges
    Begins and ends at the same vertex],
  [A closed trail is a trail that begins and ends at the same vertex. It is commonly called a #strong[circuit].], [#emph[d] → #emph[f] → #emph[b] → #emph[c] → #emph[f] → #emph[e] → #emph[d]], [No repeated edges
    Begins and ends at the same vertex],
  [A closed path is a path that begins and ends at the same vertex. It is also referred to as a #strong[directed cycle] because it travels through a cyclic subgraph.], [#emph[d] → #emph[f] → #emph[b] → #emph[c] → #emph[d]], [No repeated edges or vertices
    Begins and ends at the same vertex],
))


    Since walks, trails, and paths are all related, closed walks, circuits, and directed cycles are related too.


    + All circuits are closed walks, but closed walks that visit the same edge twice are not circuits.
+ All directed cycles are circuits, but circuits in which a vertex is visited twice are not directed cycles.


    We can visualize the relationship as in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-45.54pt, -26.29pt), (45.54pt, -26.29pt), stroke: 0.7pt + black)
  line((45.54pt, -26.29pt), (0.00pt, 52.59pt), stroke: 0.7pt + black)
  circle((0.00pt, 52.59pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-3.60pt, 71.29pt), anchor: "south", text(size: 9pt)[directed cycles])
  circle((45.54pt, -26.29pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((60.66pt, -33.65pt), anchor: "north-west", text(size: 9pt)[circuits])
  circle((-45.54pt, -26.29pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-60.66pt, -33.65pt), anchor: "north-east", text(size: 9pt)[closed walks])
  line((45.82pt, -23.72pt), (41.54pt, -26.29pt), (45.82pt, -28.87pt), fill: black, stroke: none, close: true)
  line((-2.37pt, 51.54pt), (2.00pt, 49.12pt), (2.09pt, 54.12pt), fill: black, stroke: none, close: true)
})]),
  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 same circuit can be named using any of its vertices as a starting point. For example, the circuit #emph[d] → #emph[f] → #emph[b] → #emph[c] → #emph[d] can also be referred to in the following ways.


    #emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[a] is the same as


    #math.equation(block: true, alt: "{ b → c → d → a → b; c → d → a → b → c; d → a → b → c → d")[$\{ b → c → d → a → b \ c → d → a → b → c \ d → a → b → c → d$]
    Let’s practice working with closed walks, circuits (closed trails), and directed cycles (closed paths). In the graph in , the vertices are major central and south Florida airports. The edges are direct flights between them.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[TPA])
  circle((36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[MCO])
  circle((36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[PBI])
  circle((0.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[FLL])
  circle((-36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[MIA])
  circle((-36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[EYW])
  line((-28.84pt, 22.38pt), (-26.41pt, 26.75pt), (-31.41pt, 26.84pt), fill: black, stroke: none, close: true)
  line((-30.53pt, -16.04pt), (-30.62pt, -11.04pt), (-35.00pt, -13.46pt), fill: black, stroke: none, close: true)
  line((2.58pt, -34.78pt), (0.00pt, -30.50pt), (-2.58pt, -34.78pt), fill: black, stroke: none, close: true)
  line((35.00pt, -13.46pt), (30.62pt, -11.04pt), (30.53pt, -16.04pt), fill: black, stroke: none, close: true)
  line((-29.16pt, 18.42pt), (-24.87pt, 21.00pt), (-29.16pt, 23.58pt), fill: black, stroke: none, close: true)
  line((-28.84pt, -19.62pt), (-26.41pt, -15.25pt), (-31.41pt, -15.16pt), fill: black, stroke: none, close: true)
  line((5.84pt, -37.04pt), (5.75pt, -32.04pt), (1.38pt, -34.46pt), fill: black, stroke: none, close: true)
  line((-1.38pt, -34.46pt), (-5.75pt, -32.04pt), (-5.84pt, -37.04pt), fill: black, stroke: none, close: true)
})]),
  alt: "A graph represents the direct flights between Central and South Florida airports. The graph has six vertices: T P A, M C O, P B I, F L L, M I A, and E Y W. Edges from T P A lead to E Y W, M I A, F L L, and P B I. Edges from M C O lead to E Y W, M I A, and F L L. An edge from E Y W leads to F L L.", caption: [Major Central and South Florida Airports],
)


    #examplebox("Example 3")[Determining a Closed Walk, Circuit, or Directed Cycle][
Suppose that you need to travel by air from Miami (MIA) to Orlando (MCO) and you were restricted to flights represented on the graph. For the trip to Orlando, you decide to purchase tickets with a layover in Key West (EYW) as shown in , but you still have to decide on the return trip. Determine if your roundtrip itinerary is a closed walk, a circuit, and/or a directed cycle, based on the return trip described in each part.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  bezier((36.37pt, 21.00pt), (-36.37pt, 21.00pt), (0.00pt, 25.20pt), 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((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  bezier((-36.37pt, 21.00pt), (36.37pt, 21.00pt), (0.00pt, 25.20pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[TPA])
  circle((36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[MCO])
  circle((36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[PBI])
  circle((0.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[FLL])
  circle((-36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[MIA])
  circle((-36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[EYW])
  line((-38.95pt, 13.78pt), (-36.37pt, 9.50pt), (-33.80pt, 13.78pt), fill: black, stroke: none, close: true)
  line((40.92pt, 23.07pt), (36.37pt, 21.00pt), (40.33pt, 17.95pt), fill: black, stroke: none, close: true)
})]),
  alt: "A graph represents the direct flights between Central and South Florida airports. The graph has six vertices: T P A, M C O, P B I, F L L, M I A, and E Y W. Edges from T P A lead to E Y W, M I A, F L L, and P B I. Edges from M C O lead to E Y W, M I A, and F L L. An edge from E Y W leads to F L L. An arrow from M I A points to E Y W. An arrow from E Y W points to M C O.", caption: [MIA to EYW to MCO],
)


        + You returned to Miami (MIA) by reversing your route.
+ Your direct flight back left Orlando (MCO) but was diverted to Fort Lauderdale (FLL)! From there you flew to Tampa (TPA) before returning to Miami (MIA).


      
      #solutionbox[
+ The whole trip was #emph[MIA] → #emph[EYW] → #emph[MCO] → #emph[EYW] → #emph[MIA]. This is a closed walk, because it is a walk that begins and ends at the same vertex. It is not a circuit, because it repeats edges. If it is not a circuit, then it cannot be a directed cycle.
+ The whole trip was #emph[MIA] → #emph[EYW] → #emph[MCO] → #emph[FLL] → #emph[TPA] → #emph[MIA]. This is a closed walk, because it is a walk that begins and ends at the same vertex. It is a circuit because no edges were repeated. It is also a directed cycle because no vertices were repeated either. So, it is all three!
]
]


    
    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/closed_walks")[Closed Walks, Closed Trails (Circuits), and Closed Paths (Directed Cycles) in Graph Theory]
]


  
  
    
=== Graph Colorings


    In this section so far, we have looked at how to navigate graphs by proceeding from one vertex to another in a sequence that does not skip any vertices, but in some applications we may want to skip vertices. Remember the camp Olympics at Camp Woebegone in Comparing Graphs? You were planning a camp Olympics with four events. The campers signed up for the events. You drew a graph to help you visualize which events have campers in common. The vertices of Graph #emph[E] in  represent the events and adjacent vertices indicate that there are campers who are participating in both.


    #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), (-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])
})]),
  alt: "A graph with four vertices: a, b, c, and d. The edges connect a b, b d, d c, and c a.", caption: [Graphs of Camp Olympics],
)


    In this case, we do NOT want events represented by two adjacent vertices to occur in the same timeslot, because that would prevent the campers who wanted to participate in both from doing so. We can use the graph in  to count the timeslots we need so there are no conflicts. Let’s assign each timeslot a different color. We could categorize events that happen at 1 pm as Red; 2 pm, Purple; 3 pm, Blue; and 4 pm, Green. Then assign different colors to any pair of adjacent vertices to ensure that the events they represent do not end up in the same timeslot.  shows several of the ways to do this while obeying the rule that no pair of adjacent vertices can be the same color.


    #figure(
  stdfig([#grid(columns: 3, 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 1])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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: rgb("#1d56a6"), stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: white)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: rgb("#00874a"), stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: white)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: rgb("#800080"), stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: white)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: rgb("#d62128"), stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: white)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph 2])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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: rgb("#1d56a6"), stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: white)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: rgb("#800080"), stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: white)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: rgb("#800080"), stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: white)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: rgb("#d62128"), stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: white)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph 3])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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: rgb("#d62128"), stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: white)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: rgb("#800080"), stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: white)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: rgb("#800080"), stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: white)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: rgb("#d62128"), stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: white)[d])
})]
)]),
  alt: "Three graphs are labeled graph 1, graph 2, and graph 3. Graph 1 has four vertices: a, b, c, and d in blue, green, purple, and red, respectively. Graph 2 has four vertices: a, b, c, and d in blue, purple, purple, and red, respectively. Graph 3 has four vertices: a, b, c, and d in red, purple, purple, and red, respectively. In each graph, the edges connect a b, b d, d c, and c a.", caption: [Graph Colorings],
)


    In , the graphs with vertices colored so that no adjacent vertices are the same color are called #strong[graph colorings]. Notice that Graph 3 has the fewest colors, which means it shows us how to have the fewest number of timeslots. The events marked in red, #emph[a] and #emph[d], can be held at the same time because they are not adjacent and do not have conflicts. Also, the events marked in purple, #emph[b] and #emph[c], can be held at the same time. We would not need green or blue timeslots at all!


    A graph that uses #math.equation(block: false, alt: "n")[$n$] colors is called an #strong[#math.equation(block: false, alt: "n")[$bold(italic(n))$]-coloring]. The smallest number of colors needed to color a particular graph is called its #strong[chromatic number].


    Graph colorings can be used in many applications like the scheduling scenario at camp Woebegone. Let's look at how they work in more detail.  shows two different colorings of a particular graph. Coloring A is called a four-coloring, because it uses four colors, red (R), green (G), blue (B), and purple (P). Coloring B is called a three-coloring because it uses three. The colors allow us to visually subdivide the graphs into groups. The only rule is that adjacent vertices are different colors so that they are in different groups.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[coloring A])
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (47.60pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (0.00pt, -84.00pt), (18.03pt, -60.03pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (58.05pt, -67.95pt), stroke: 0.7pt + black)
  line((42.00pt, -42.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (61.35pt, -64.65pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (0.00pt, -84.00pt), (23.97pt, -65.97pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (47.60pt, -63.00pt), stroke: 0.7pt + black)
  circle((42.00pt, -29.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (64.65pt, -61.35pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (67.95pt, -58.05pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), 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)[G])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[G])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[P])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[P])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[G])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[coloring B])
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -88.20pt), stroke: 0.7pt + black)
  line((42.00pt, -84.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), 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)[G])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[G])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[G])
})]
)]),
  alt: "Two graphs are labeled coloring A and coloring B In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: B, G, and R. Row 2: G, R, and P. Row 3: P, B, and G. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect G R, R B, G R, and R P. Diagonal lines connect B R, R G, G B, and G P. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: B, G, and R. Row 2: G, R, and B. Row 3: R, B, and G. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect G R, R B, G R, and R B. Diagonal lines connect B R, R G, G B, and G B.", caption: [Two Colorings of the Same Graph],
)


    It turns out that a three-coloring is the best we can do with the graph in . No matter how many different patterns you try with only two colors, you will never find one in which the adjacent vertices are always different colors. In other words, the graph has a chromatic number of three. For large graphs, computer assistance is usually required to find the chromatic numbers. There is no formula for finding the chromatic number of a graph, but there are some facts that are helpful in .


    #figure(table(
  columns: 2, align: left, inset: 6pt,
  table.header([Fact], [Example]),
  [Recall that planar graphs are untangled; that is, they can be drawn on a flat surface so that no two edges are crossing.#strong[If a graph is planar, it can be colored with four colors or possibly fewer.]], [],
  [Each vertex in a complete graph is adjacent to every other vertex forcing us to color them all different colors.#strong[The chromatic number of a complete graph is the same as the number of vertices.]], [],
  [If a graph has a clique, a complete subgraph, then each vertex in the clique must have a different color and the vertices outside the clique may or may not have even more colors. #strong[The chromatic number of a graph is #emph[at least] the number of vertices in its biggest clique.]], [],
))


  
  
    
=== Creating Colorings to Solve Problems


    Let’s see how these facts can help us color the graph in .


    - Since the graph is planar, the chromatic number is #emph[no more than] four.
- The graph is not complete, but it has complete subgraphs of three vertices. In other words, it has triangles like the one shown with blue vertices in . This means that the chromatic number is #emph[at least] three.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (84.00pt, 0.00pt), stroke: 0.7pt + black)
  line((84.00pt, 0.00pt), (84.00pt, -42.00pt), stroke: 0.7pt + black)
  line((84.00pt, -42.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((42.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, -42.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, -42.00pt), (84.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, -42.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: rgb("#808080"), stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: white)[TL])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[TC])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[TR])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: rgb("#808080"), stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: white)[ML])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: rgb("#808080"), stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: white)[MC])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[MR])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[BL])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[BC])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[BR])
})]),
  alt: "A graph has nine vertices arranged in 3 rows and 3 columns. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. The vertices at the top-left, left-center, and center are highlighted in grey.", caption: [A Graph with Triangles],
)


    We know we can color this graph in three or four colors. It is usually best to start by coloring the vertex of highest degree as shown. In this case, we used red (R). The color is not important.


    #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)[degrees of vertices])
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -42.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[6])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[degree 6 vertex colored first])
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -42.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})]
)]),
  alt: "Two graphs are labeled degrees of vertices and degree 6 vertex colored first. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 2: 4, 6, and 4. Row 3: 2, 4, and 3. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 3: 4, R, and 4. Row 3: 2, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.", caption: [Color Highest Degree Vertex First],
)


    We want to color as many of the vertices the same color as possible; so, we look at all the vertices that are not adjacent to the red vertex and begin to color them, red starting with the one among them of highest degree. Since the only vertices that are not adjacent are both degree 2, choose either one and color it red as shown.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (39.67pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (49.00pt, -63.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -42.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (51.80pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (36.12pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (43.96pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (43.96pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (42.00pt, -42.00pt), (36.12pt, -63.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (42.00pt, -84.00pt), (51.80pt, -63.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -42.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  bezier((42.00pt, -42.00pt), (84.00pt, -84.00pt), (65.97pt, -60.03pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})]
)]),
  alt: "Two graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 3: 4, R, and 4. Row 3: 2, 4, and 3. 2 in the top-right and bottom-left vertices are outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and R. Row 2: 4, R, and 4. Row 3: 2, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.", caption: [Color More Red from Highest to Lowest Degree],
)


    Now, there is only one vertex left that is not adjacent to a red; so, color it red. Of the remaining vertices, the highest degree is four; so, color one of the vertices of degree four in a different color. These two steps are shown.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -74.20pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -78.12pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -85.96pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -82.04pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -89.88pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -74.20pt), stroke: 0.7pt + black)
  circle((42.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -77.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -79.80pt), stroke: 0.7pt + black)
  circle((42.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((42.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((84.00pt, -84.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -88.20pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -89.60pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((42.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -78.40pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -79.80pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  circle((42.00pt, -71.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})]
)]),
  alt: "Two graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and R. Row 3: 4, R, and 4. Row 3: R, 4, and 3. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: 4, R, and 4. Row 3: R, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.", caption: [Complete the Reds and Start Another Color],
)


    Repeat the same procedure. There are three remaining vertices that are not adjacent to a blue. Color as many blue as possible, with priority going to vertices of higher degree as shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((84.00pt, -84.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((42.00pt, -84.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((84.00pt, -84.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((42.00pt, -84.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 0.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  line((42.00pt, -84.00pt), (0.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[4])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
})]
)]),
  alt: "Three graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 3: 4, R, and 4. Row 3: R, 4, and 3. 4 in the left-center and bottom-center vertices are outlined. 3 in the bottom-right vertex is outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and 4. Row 3: R, 4, and 3. 3 in the bottom-right vertex is outlined. In the third graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and 4. Row 3: R, 4, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph. An arrow from the second graph points to the third graph.", caption: [Repeat Procedure for Color Blue],
)


    All the remaining vertices are adjacent to blue. So, it is time to repeat the procedure with another color as shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  bezier((0.00pt, 0.00pt), (84.00pt, -84.00pt), (39.03pt, -44.97pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -42.00pt), (43.88pt, -66.76pt), stroke: 0.7pt + black)
  line((84.00pt, -42.00pt), (84.00pt, -84.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, 0.00pt), (39.03pt, -44.97pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -42.00pt), (40.12pt, -59.24pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[P])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[4])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
})],
  [#cetz.canvas({
  import cetz.draw: *
  bezier((0.00pt, 0.00pt), (84.00pt, -84.00pt), (39.03pt, -44.97pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -91.00pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -81.67pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, 0.00pt), (39.03pt, -44.97pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -81.67pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -77.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[P])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[P])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
})],
  [#cetz.canvas({
  import cetz.draw: *
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -91.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -92.40pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -91.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -92.40pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[P])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[P])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[P])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
})]
)]),
  alt: "Three graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 3: B, R, and P. Row 3: R, 4, and B. 3 in the top-left vertex is outlined. 4 in the bottom-center is outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. 3 in the top-left vertex is outlined. In the third graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: P, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph. An arrow from the second graph points to the third graph.", caption: [Repeat Procedure for Color Purple],
)


    All the vertices are now colored with a three-coloring so we know the chromatic number is #emph[at most] three, but we knew the chromatic number was #emph[at least] three because the graph has a triangle. So, we are now certain it is #emph[exactly]three.


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Coloring_and_Identifying")[Coloring Graphs Part 1: Coloring and Identifying Chromatic Number]
]


    Suppose the vertices of the graph in  represented the nine events in the Camp Woebegone Olympics, and edges join any events that have campers in common, but nonadjacent vertices do not.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -91.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -92.40pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (84.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -86.33pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (42.00pt, -84.00pt), (63.00pt, -91.00pt), stroke: 0.7pt + black)
  line((84.00pt, -84.00pt), (0.00pt, -84.00pt), stroke: 0.7pt + black)
  line((0.00pt, -84.00pt), (42.00pt, -84.00pt), stroke: 0.7pt + black)
  bezier((84.00pt, -84.00pt), (0.00pt, -84.00pt), (42.00pt, -88.20pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (42.00pt, -84.00pt), (21.00pt, -79.80pt), stroke: 0.7pt + black)
  bezier((42.00pt, -84.00pt), (0.00pt, -84.00pt), (21.00pt, -92.40pt), stroke: 0.7pt + black)
  bezier((0.00pt, -84.00pt), (84.00pt, -84.00pt), (42.00pt, -75.60pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), text(size: 9pt, fill: black)[P])
  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((84.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, 0.00pt), text(size: 9pt, fill: black)[R])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[R])
  circle((84.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -42.00pt), text(size: 9pt, fill: black)[P])
  circle((0.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -84.00pt), text(size: 9pt, fill: black)[R])
  circle((42.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -84.00pt), text(size: 9pt, fill: black)[P])
  circle((84.00pt, -84.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.00pt, -84.00pt), text(size: 9pt, fill: black)[B])
})]),
  alt: "A graph has nine vertices. The vertices are arranged in 3 rows and 3 columns. Row 1: P, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines.", caption: [Coloring for Nine Event Camp Woebegone Olympics],
)


    Any vertices of the same color are nonadjacent; so, they have no conflicts. Since this graph is a three-coloring, all nine events could be scheduled in just three timeslots!


    #examplebox("Example 4")[Understanding Chromatic Numbers][
In Example 5 in Section 12.3, we discussed a high school, which holds end-of-course exams in (E3) English 3, (E4) English 4, (M) Advanced Math, (C) Calculus, (W) World History, (U) U.S. History, (B) Biology, and (P) Physics. We were given a list of courses that had no students in common. We used that information to find the graph in , which shows edges between exams with students in common. Use the graph we found in Example 5 in Section 12.3 to answer each question.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-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((42.00pt, 0.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-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), (-29.70pt, 29.70pt), 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)[P])
  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)[U])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[W])
  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((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[M])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[E4])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[E3])
  line((-23.43pt, 29.50pt), (-20.46pt, 33.53pt), (-25.40pt, 34.27pt), fill: black, stroke: none, close: true)
  line((25.40pt, 34.27pt), (20.46pt, 33.53pt), (23.43pt, 29.50pt), 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((29.89pt, -23.43pt), (25.87pt, -20.46pt), (25.13pt, -25.40pt), 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)
  line((42.19pt, 6.27pt), (38.17pt, 9.24pt), (37.43pt, 4.29pt), fill: black, stroke: none, close: true)
  line((32.28pt, -23.98pt), (29.70pt, -19.70pt), (27.12pt, -23.98pt), fill: black, stroke: none, close: true)
  line((4.57pt, -37.71pt), (3.83pt, -32.76pt), (-0.19pt, -35.73pt), fill: black, stroke: none, close: true)
  line((-23.83pt, -27.48pt), (-22.63pt, -22.63pt), (-27.48pt, -23.83pt), fill: black, stroke: none, close: true)
  line((-35.73pt, -0.19pt), (-32.76pt, 3.83pt), (-37.71pt, 4.57pt), fill: black, stroke: none, close: true)
  line((-25.40pt, 25.13pt), (-20.46pt, 25.87pt), (-23.43pt, 29.89pt), fill: black, stroke: none, close: true)
  line((-23.43pt, -29.89pt), (-20.46pt, -25.87pt), (-25.40pt, -25.13pt), 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((-37.71pt, -4.57pt), (-32.76pt, -3.83pt), (-35.73pt, 0.19pt), fill: black, stroke: none, close: true)
  line((-23.98pt, -32.28pt), (-19.70pt, -29.70pt), (-23.98pt, -27.12pt), fill: black, stroke: none, close: true)
  line((6.27pt, -42.19pt), (9.24pt, -38.17pt), (4.29pt, -37.43pt), fill: black, stroke: none, close: true)
  line((-29.89pt, 23.43pt), (-25.87pt, 20.46pt), (-25.13pt, 25.40pt), fill: black, stroke: none, close: true)
  line((-32.28pt, 23.98pt), (-29.70pt, 19.70pt), (-27.12pt, 23.98pt), fill: black, stroke: none, close: true)
})]),
  alt: "A graph has eight vertices. The vertices are P, B, U, W, C, M, E 4, and E 3. Edges from P lead to E 3, B, U, W, and C. Edges from B lead to U, W, C, M, and E 4. Edges from U lead to E 3, M, and C. Edges from W lead to E 4, M, and C. An edge from C leads to E 3. An edge from M leads to E 3.", caption: [Graph of Exams with Students in Common],
)


        + The graph contains a clique of size 4 formed by the vertices P, E3, C, and U. What does this tell you about the chromatic number?
+ The graph is not planar, meaning that you cannot untangle it. What does this tell you about the chromatic number?
+ Create a coloring by coloring vertex of highest degree first, coloring as many other vertices as possible each color from highest to lowest degree, then repeating this process for the remaining vertices.
+ Do you know what the minimum number of timeslots is? If so, what is it and how do you know? If not, what are the possibilities?


      
      #solutionbox[
+ We would need four different colors just for the clique with four vertices; so, the chromatic number is #emph[at least] four.
+ It is possible for the chromatic number to be greater than four.
+ The process is shown.
    #figure(table(
  columns: 3, align: left, inset: 6pt,
  table.header([], [], []),
  [This is the original graph. Vertex B has highest degree.], [Color vertex B. Vertex E3 is the only remaining vertex that is NOT adjacent to B.], [Color vertex E3 the same color. Vertices P, U, W, and C are the remaining vertices with highest degree. Pick one to color.],
  [], [], [],
  [Color vertex P a new color. Vertices E4 and M are NOT adjacent to P, and M has higher degree.], [Color vertex M the same color. Vertex E4 is the only remaining vertex NOT adjacent to P or M.], [Color vertex E4 the same color. Vertices U, W, and C are the remaining vertices with highest degree. Pick one to color.],
  [], [], [],
  [Color U a new color. Vertex W is the only remaining vertex NOT adjacent to U.], [Color vertex W the same color. Vertex C is the only remaining vertex that has NOT been colored.], [Color vertex C a new color. The coloring is final. We used four colors.],
))

The last graph in  is the final coloring.
+ Yes, the minimum number of times slots is the chromatic number. We knew the chromatic number had to be at least four because there was a clique with four vertices. Now we have found a four-coloring of the graph which tells us that the chromatic number is at most four. So, we know four must be the chromatic number.
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[The procedure used in Example 22 to color the graph is not guaranteed to result in a graph that has the minimum number of colors possible, but it is usually results in a coloring that is close to the chromatic number.]
]


    
  
  
    
=== The Four Color Problem


    #figure(figph[Two figures. The first figure shows a rectangle divided into several small blocks. The second figure is the same as that of the first figure with the addition that the blocks are shaded in 4 different colors.], alt: "Two figures. The first figure shows a rectangle divided into several small blocks. The second figure is the same as that of the first figure with the addition that the blocks are shaded in 4 different colors.", caption: [Using only four colors, no two adjacent regions have the same color.])


    The idea of coloring graphs to solve problems was inspired by one of the most famous problems in mathematics, the “four color problem.” The idea was that, no matter how complicated a map might be, only four colors were needed to color the map so that no two regions that shared a boundary would be the same color. For many years, everyone suspected this to be true, because no one could create a map that needed more than four colors, but they couldn’t prove it was true in general. Finally, graphs were used to solve the problem!


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/The_Four")[The Four Color Map Theorem – Numberphile]
]


    We saw how maps can be represented as graphs in Graph Basics.  from Example 4 in Section 12.1 shows a map of the midwestern region of the United States.


    #figure(figph[A partial map of the USA with midwestern states. The Midwestern states are North Dakota, South Dakota, Nebraska, Kansas, Minnesota, Iowa, Missouri, Wisconsin, Illinois, Indiana, Michigan, and Ohio.], alt: "A partial map of the USA with midwestern states. The Midwestern states are North Dakota, South Dakota, Nebraska, Kansas, Minnesota, Iowa, Missouri, Wisconsin, Illinois, Indiana, Michigan, and Ohio.", caption: [Map of Midwestern States])


    shows how this map can be associated with a graph in which each vertex represents a state and each edge indicates the states that share a common boundary.  shows the final graph.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 54.25pt), (27.12pt, 46.98pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((27.12pt, 46.98pt), (46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((27.12pt, 46.98pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((27.12pt, 46.98pt), (46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (-27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-27.12pt, -46.98pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((-27.12pt, -46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, -27.12pt), (-54.25pt, -0.00pt), stroke: 0.7pt + black)
  line((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((-54.25pt, -0.00pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  line((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 54.25pt), text(size: 9pt, fill: black)[ND])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), text(size: 9pt, fill: black)[SD])
  circle((46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, 27.12pt), text(size: 9pt, fill: black)[NE])
  circle((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[KS])
  circle((46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, -27.12pt), text(size: 9pt, fill: black)[MN])
  circle((27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, -46.98pt), text(size: 9pt, fill: black)[IA])
  circle((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[MO])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[WI])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[IL])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[IN])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[MI])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[OH])
})]),
  alt: "A partial map of the USA with midwestern states. The Midwestern states are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H). Edges from N D connect with S D and M N. Edges from S D connect with N E, I A, and M N. Edges from M N connect with I A and W I. Edges from N E connect with K S, M O, and I A. Edges from I A connect with M O and I L. Edges from W I connect with I A and I L. An edge from K S connects with M O. An edge from M O connects with I L. An edge from I L connects with I N. Edges from I N connect with M I and O H. An edge from M I connects with O H.", caption: [Edge Assigned to Each Pair of Midwestern States with Common Border],
)


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((46.98pt, -27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (-27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((46.98pt, 27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-27.12pt, -46.98pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((-27.12pt, -46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, -27.12pt), (-54.25pt, -0.00pt), stroke: 0.7pt + black)
  line((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((-54.25pt, -0.00pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  line((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 54.25pt), text(size: 9pt, fill: black)[ND])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), text(size: 9pt, fill: black)[SD])
  circle((46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, 27.12pt), text(size: 9pt, fill: black)[NE])
  circle((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[KS])
  circle((46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, -27.12pt), text(size: 9pt, fill: black)[MN])
  circle((27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, -46.98pt), text(size: 9pt, fill: black)[IA])
  circle((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[MO])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[WI])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[IL])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[IN])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[MI])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[OH])
})]),
  alt: "A graph represents common boundaries between midwestern states. The vertices are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H). Edges from M N connect with I A and W I. Edges from N E connect with K S, M O, and I A. Edges from I A connect with M O and I L. Edges from W I connect with I A and I L. An edge from K S connects with M O. An edge from M O connects with I L. An edge from I L connects with I N. Edges from I N connect with M I and O H. An edge from M I connects with O H.", caption: [Final Graph Representing Common Boundaries between Midwestern States],
)


    Notice that the graph representing the common boundaries between midwestern states is planar, meaning that it can be drawn on a flat surface without edges crossing. As we have seen, any planar graph has a chromatic number of four or less. This very well-known fact is called the #strong[Four-Color Theorem], or #strong[Four-Color Map Theorem].


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Coloring_Maps")[Coloring Graphs Part 2: Coloring Maps and the Four Color Problem]
]


    #notebox("People in Mathematics", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Four-Color Theorem]


      In the 19th century, Francis Guthrie was coloring a map of British counties and noticed that he could color so that no two adjacent counties were the same color using only four colors. This seemed to be the case for other maps as well, but he could not figure out why. He shared this with his brother, Frederick, who subsequently took the problem to his professor, August De Morgan, one of the most famous mathematicians of all time. De Morgan never was able to solve the problem, but he shared it with his colleagues. The problem continued to intrigue and perplex mathematicians for over a hundred years, inspiring discoveries in several areas of mathematics. It was finally proven by Kenneth Appel and Wolfgang Haken from the University of Illinois in 1976 using a combination of computer-aided calculations and graph theory. This was the first time in history that a mathematical theorem was proven using a computer! (Jesus Najera, “The Four-Color Theorem,” #emph[Cantor’s Paradise], a Medium publication, October 22, 2019)
]


    #examplebox("Example 5")[Using Four Colors or Fewer to Color a Graph][
Find a coloring of the graph in , which uses four colors or fewer. Use the resulting coloring as a guide to recolor the map in . How many colors did you use? Does this support the conclusion of the Four-Color Theorem? If so, how?


      
      #solutionbox[
The steps to color the graph are shown.


        #figure(table(
  columns: 3, align: left, inset: 6pt,
  table.header([], [], []),
  [#strong[Step 1:] Graph with degrees of vertices labeled.
    Vertex IA has highest degree.], [#strong[Step 2:] Color vertex IA any color.
    Vertices ND, KS, MI, OH, and IN are NOT adjacent to IA.
    MI and IN have highest degree, 3.], [#strong[Step 3:] Color either MI or IN the same color as IA.
    Vertex ND and KS are the only remaining vertices not adjacent to a red vertex.
    They both have degree 2.],
  [], [], [],
  [#strong[Step 4:] Since KS and ND are not adjacent to each other, we can save a step and color both red. The highest degree of remaining vertices is four.], [#strong[Step 5:] Choose one of the vertices of degree 4, SD, to color with a new color, blue. The vertices WI, IL, MO, IN,and OH are NOT adjacent to blue.
    WI, IL, and MO have the highest degree.], [#strong[Step 6:] Choose one of WI, IL, or MO to color.
    We color WI blue.
    MO, IN and OH are NOT adjacent to blue.
    MO has the highest degree of these.],
  [], [], [],
  [#strong[Step 7:] Color MO blue. All remaining vertices are adjacent to blue.
    Choose a new color. Four vertices remain, MN, NE, IL, and OH. MN, NE, and IL have the highest degree.], [#strong[Step 8:] Since MN, IL, and NE are not adjacent, save steps and color all three the new color, purple.
    Vertex OH is the only remaining vertex that has NOT been colored.], [#strong[Step 9:] Since vertex OH is not adjacent to purple, color it purple.
    This is the final graph.
    We used three colors.],
))


        The final graph in  shows how we would color the map. In  we have colored the map to correspond to the colors on the graph.


        #figure(figph[A partial map of the USA with midwestern states. The Midwestern states are North Dakota, South Dakota, Nebraska, Kansas, Minnesota, Iowa, Missouri, Wisconsin, Illinois, Indiana, Michigan, and Ohio. North Dakota, Kansas, Iowa, and Michigan are in red. South Dakota, Missouri, Wisconsin, and Indiana are in blue. Nebraska, Minnesota, Illinois, and Ohio are in purple.], alt: "A partial map of the USA with midwestern states. The Midwestern states are North Dakota, South Dakota, Nebraska, Kansas, Minnesota, Iowa, Missouri, Wisconsin, Illinois, Indiana, Michigan, and Ohio. North Dakota, Kansas, Iowa, and Michigan are in red. South Dakota, Missouri, Wisconsin, and Indiana are in blue. Nebraska, Minnesota, Illinois, and Ohio are in purple.", caption: [Midwestern States in Three Colors])


        We used three colors to color the graph. This supports the Four-Color Theorem, because the graph is planar and its chromatic number is less than four.
]
]


    
    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Coloring A Möbius Strip]


      Have you ever heard of a möbius strip? It is a flat object with only one side. This might sound theoretical, but you can make one for yourself. Take a narrow strip of paper, make a half twist in it, and tape the ends together. To prove to yourself that it has only one side, pick a point anywhere on the paper and start drawing a line. You can draw the line continuously without lifting your pen from the paper and eventually, you will get back to the point at which you started. Since you never had to flip over the paper, you have just proved it has one side!


      Now, you might be wondering what this has to do with Graph Theory. It turns out that a map drawn on a möbius strip cannot necessarily be drawn using four colors. This doesn’t contradict the Four-Color Theorem, which only applies to graphs that are planar. A möbius strip does not live on a “plane,” or flat surface, which means the maps are not always planar like those drawn on a flat piece of paper. In the case of a möbius strip, it is the Six-Color Map Theorem!  is an example of a möbius strip with a map that requires five colors.


      #figure(figph[A Mobius strip is shaded in five different colors.], alt: "A Mobius strip is shaded in five different colors.", caption: [A Five-Coloring on a Möbius Strip])
]


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Neil_de_Grasse")[Neil deGrasse Tyson Explains the Möbius Strip]
]


  
  
  
  
    
=== Key Terms


    - walk (directed walk)
- trail (directed trail)
- path (directed path)
- closed
- open
- closed walk
- circuit (closed trail)
- directed cycle (closed path)
- coloring (graph coloring)
- #math.equation(block: false, alt: "n")[$n$]-coloring
- chromatic number


  
  
    
=== Key Concepts


    - Walks, trails, and paths are ways to navigate through a graph using a sequence of connected vertices and edges.
- Closed walks, circuits, and directed cycles are ways to navigate from a vertex on a graph and return to the same vertex.
- Colorings are a way to organize the vertices of a graph into groups so that no two members of a group are adjacent.
- Maps can be represented with planar graphs, which can always be colored using four colors or fewer.


  
  
    
=== Videos


    - #link("https://openstax.org/r/walks_trails_paths")[Walks, Trails, and Paths in Graph Theory]
- #link("https://openstax.org/r/closed_walks")[Closed Walks, Closed Trails (Circuits), and Closed Paths (Directed Cycles) in Graph Theory]
- #link("https://openstax.org/r/Coloring_and_Identifying")[Coloring Graphs Part 1: Coloring and Identifying Chromatic Number]
- #link("https://openstax.org/r/The_Four")[The Four Color Map Theorem – Numberphile]
- #link("https://openstax.org/r/Coloring_Maps")[Coloring Graphs Part 2: Coloring Maps and the Four Color Problem]
- #link("https://openstax.org/r/Neil_de_Grasse")[Neil deGrasse Tyson Explains the Möbius Strip]