#set document(title: "12.10 Trees", 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.10#h(0.6em)Trees


  #figure(figph[A row of trees with no leaves.], alt: "A row of trees with no leaves.", caption: [In graph theory, graphs known as trees have structures in common with live trees.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Describe and identify trees.
+ Determine a spanning tree for a connected graph.
+ Find the minimum spanning tree for a weighted graph.
+ Solve application problems involving trees.


  
  We saved the best for last! In this last section, we will discuss arguably the most fun kinds of graphs, trees. Have you every researched your family tree? Family trees are a perfect example of the kind of trees we study in graph theory. One of the characteristics of a family tree graph is that it never loops back around, because no one is their own grandparent!


  
    
=== What Is A Tree?


    Whether we are talking about a family tree or a tree in a forest, none of the branches ever loops back around and rejoins the trunk. This means that a #strong[tree] has no cyclic subgraphs, or is #strong[acyclic]. A tree also has only one component. So, a tree is a connected acyclic graph. Here are some graphs that have the same characteristic. Each of the graphs in  is a tree.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 88.53pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, 67.53pt), (27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (-14.04pt, -66.05pt), stroke: 0.7pt + black)
  line((-14.04pt, -66.05pt), (-39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((-39.69pt, -54.63pt), (-58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((-58.48pt, -33.76pt), (-27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (-67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((58.48pt, -33.76pt), (39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((39.69pt, -54.63pt), (14.04pt, -66.05pt), stroke: 0.7pt + black)
  circle((0.00pt, 67.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.53pt), text(size: 9pt, fill: black)[a])
  circle((27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.47pt, 61.69pt), text(size: 9pt, fill: black)[b])
  circle((50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.18pt, 45.19pt), text(size: 9pt, fill: black)[c])
  circle((64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.22pt, 20.87pt), text(size: 9pt, fill: black)[d])
  circle((67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((67.16pt, -7.06pt), text(size: 9pt, fill: black)[e])
  circle((58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.48pt, -33.76pt), text(size: 9pt, fill: black)[f])
  circle((39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.69pt, -54.63pt), text(size: 9pt, fill: black)[g])
  circle((14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -66.05pt), text(size: 9pt, fill: black)[h])
  circle((-14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -66.05pt), text(size: 9pt, fill: black)[i])
  circle((-39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.69pt, -54.63pt), text(size: 9pt, fill: black)[j])
  circle((-58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.48pt, -33.76pt), text(size: 9pt, fill: black)[k])
  circle((-67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-67.16pt, -7.06pt), text(size: 9pt, fill: black)[l])
  circle((-64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.22pt, 20.87pt), text(size: 9pt, fill: black)[m])
  circle((-50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-50.18pt, 45.19pt), text(size: 9pt, fill: black)[n])
  circle((-27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.47pt, 61.69pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph S])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-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)[u])
  circle((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[t])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[v])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[w])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[x])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[y])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[z])
})]
)]),
  alt: "Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z.", caption: [Graphs #emph[T], #emph[P], and #emph[S]],
)


    Let’s practice determining whether a graph is a tree. To do this, check if a graph is connected and has no cycles.


    #examplebox("Example 1")[Identifying Trees][
Identify any trees in . If a graph is not a tree, explain how you know.


        #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 M])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (18.22pt, -37.84pt), 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)[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])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph N])
  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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.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)[I])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[j])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[l])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[k])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[m])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  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((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})]
)]),
  alt: "Three graphs. Graph M has 7 vertices. The edges are a b, b f, f g, f c, b c, b d, and d e. Graph N has 6 vertices. The edges are I j, I h, l k, and l m. The edges, I j, and l k intersect each other. Graph P has 6 vertices. The edges are s t, s r, r q, q p, and p o.", caption: [Graphs #emph[M], #emph[N], and #emph[P]],
)


      
      #solutionbox[
- Graph #emph[M] is not a tree because it contains the cycle (#emph[b], #emph[c], #emph[f]).
- Graph #emph[N] is not a tree because it is not connected. It has two components, one with vertices #emph[h, i, j], and another with vertices #emph[k, l, m].
- Graph #emph[P] is a tree. It has no cycles and it is connected.
]
]


    
  
  
    
=== Types of Trees


    Mathematicians have had a lot of fun naming graphs that are trees or that contain trees. For example, the graph in  is not a tree, but it contains two components, one containing vertices #emph[a] through #emph[d], and the other containing vertices #emph[e] through #emph[g], each of which would be a tree on its own. This type of structure is called a #strong[forest]. There are also interesting names for trees with certain characteristics.


    - A #strong[path graph or linear graph] is a tree graph that has exactly two vertices of degree 1 such that the only other vertices form a single path between them, which means that it can be drawn as a straight line.
- A #strong[star tree] is a tree that has exactly one vertex of degree greater than 1 called a #strong[root,] and all other vertices are adjacent to it.
- A #strong[starlike tree] is a tree that has a single #strong[root] and several paths attached to it.
- A #strong[caterpillar tree] is a tree that has a central path that can have vertices of any degree, with each vertex not on the central path being adjacent to a vertex on the central path and having a degree of one.
- A #strong[lobster tree] is a tree that has a central path that can have vertices of any degree, with paths consisting of either one or two edges attached to the central path.


    Examples of each of these types of structures are given in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph F])
  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((-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)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[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)[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)[d])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[e])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[f])
  circle((-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((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[h])
})]),
  alt: "Graph F has 8 vertices. The vertices are labeled a to h. Edges connect b a, b d, b c, f e, f h, and f g.", caption: [Forest Graph F],
)


    #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 S])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (18.22pt, -37.84pt), 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)[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])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph N])
  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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.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)[I])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[j])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[l])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[k])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[m])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  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((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph Z])
  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((0.00pt, 54.25pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (-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), (-54.25pt, -0.00pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (-46.98pt, 27.12pt), 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)[a])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), text(size: 9pt, fill: black)[b])
  circle((46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, 27.12pt), text(size: 9pt, fill: black)[c])
  circle((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[d])
  circle((46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, -27.12pt), text(size: 9pt, fill: black)[e])
  circle((27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, -46.98pt), text(size: 9pt, fill: black)[f])
  circle((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[g])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[h])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[i])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[j])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[k])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[l])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 84.10pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph C])
  line((0.00pt, 63.10pt), (27.38pt, 56.85pt), stroke: 0.7pt + black)
  line((27.38pt, 56.85pt), (-27.38pt, 56.85pt), stroke: 0.7pt + black)
  line((27.38pt, 56.85pt), (49.33pt, 39.34pt), stroke: 0.7pt + black)
  line((49.33pt, 39.34pt), (49.33pt, -39.34pt), stroke: 0.7pt + black)
  line((49.33pt, 39.34pt), (61.51pt, 14.04pt), stroke: 0.7pt + black)
  line((49.33pt, 39.34pt), (-61.51pt, 14.04pt), stroke: 0.7pt + black)
  line((49.33pt, 39.34pt), (-49.33pt, 39.34pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (-49.33pt, 39.34pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (-61.51pt, 14.04pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (27.38pt, -56.85pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (0.00pt, -63.10pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (-27.38pt, -56.85pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (61.51pt, -14.04pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (-49.33pt, -39.34pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (-61.51pt, -14.04pt), stroke: 0.7pt + black)
  circle((0.00pt, 63.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 63.10pt), text(size: 9pt, fill: black)[m])
  circle((27.38pt, 56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.38pt, 56.85pt), text(size: 9pt, fill: black)[n])
  circle((49.33pt, 39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, 39.34pt), text(size: 9pt, fill: black)[o])
  circle((61.51pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((61.51pt, 14.04pt), text(size: 9pt, fill: black)[p])
  circle((61.51pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((61.51pt, -14.04pt), text(size: 9pt, fill: black)[q])
  circle((49.33pt, -39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -39.34pt), text(size: 9pt, fill: black)[r])
  circle((27.38pt, -56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.38pt, -56.85pt), text(size: 9pt, fill: black)[s])
  circle((0.00pt, -63.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -63.10pt), text(size: 9pt, fill: black)[t])
  circle((-27.38pt, -56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.38pt, -56.85pt), text(size: 9pt, fill: black)[u])
  circle((-49.33pt, -39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -39.34pt), text(size: 9pt, fill: black)[v])
  circle((-61.51pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-61.51pt, -14.04pt), text(size: 9pt, fill: black)[w])
  circle((-61.51pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-61.51pt, 14.04pt), text(size: 9pt, fill: black)[x])
  circle((-49.33pt, 39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, 39.34pt), text(size: 9pt, fill: black)[y])
  circle((-27.38pt, 56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.38pt, 56.85pt), text(size: 9pt, fill: black)[z])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 137.48pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph L])
  line((108.91pt, 41.30pt), (-77.24pt, -87.19pt), stroke: 0.7pt + black)
  line((108.91pt, 41.30pt), (-115.63pt, -14.04pt), stroke: 0.7pt + black)
  line((108.91pt, 41.30pt), (-108.91pt, -41.30pt), stroke: 0.7pt + black)
  line((108.91pt, 41.30pt), (95.86pt, 66.17pt), stroke: 0.7pt + black)
  line((95.86pt, 66.17pt), (-27.88pt, -113.09pt), stroke: 0.7pt + black)
  line((95.86pt, 66.17pt), (-54.13pt, -103.14pt), stroke: 0.7pt + black)
  line((-54.13pt, -103.14pt), (-27.88pt, 113.09pt), stroke: 0.7pt + black)
  line((95.86pt, 66.17pt), (77.24pt, 87.19pt), stroke: 0.7pt + black)
  line((77.24pt, 87.19pt), (27.88pt, -113.09pt), stroke: 0.7pt + black)
  line((27.88pt, -113.09pt), (-108.91pt, 41.30pt), stroke: 0.7pt + black)
  line((77.24pt, 87.19pt), (-0.00pt, -116.48pt), stroke: 0.7pt + black)
  line((-0.00pt, -116.48pt), (-54.13pt, 103.14pt), stroke: 0.7pt + black)
  line((77.24pt, 87.19pt), (54.13pt, 103.14pt), stroke: 0.7pt + black)
  line((54.13pt, 103.14pt), (77.24pt, -87.19pt), stroke: 0.7pt + black)
  line((77.24pt, -87.19pt), (-115.63pt, 14.04pt), stroke: 0.7pt + black)
  line((54.13pt, 103.14pt), (54.13pt, -103.14pt), stroke: 0.7pt + black)
  line((77.24pt, -87.19pt), (54.13pt, -103.14pt), stroke: 0.7pt + black)
  line((54.13pt, 103.14pt), (27.88pt, 113.09pt), stroke: 0.7pt + black)
  line((27.88pt, 113.09pt), (108.91pt, -41.30pt), stroke: 0.7pt + black)
  line((108.91pt, -41.30pt), (-115.63pt, -14.04pt), stroke: 0.7pt + black)
  line((27.88pt, 113.09pt), (95.86pt, -66.17pt), stroke: 0.7pt + black)
  line((95.86pt, -66.17pt), (-95.86pt, 66.17pt), stroke: 0.7pt + black)
  line((27.88pt, 113.09pt), (0.00pt, 116.48pt), stroke: 0.7pt + black)
  line((27.88pt, 113.09pt), (115.63pt, 14.04pt), stroke: 0.7pt + black)
  line((27.88pt, 113.09pt), (115.63pt, -14.04pt), stroke: 0.7pt + black)
  circle((0.00pt, 116.48pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 116.48pt), text(size: 9pt, fill: black)[a])
  circle((27.88pt, 113.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.88pt, 113.09pt), text(size: 9pt, fill: black)[b])
  circle((54.13pt, 103.14pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.13pt, 103.14pt), text(size: 9pt, fill: black)[c])
  circle((77.24pt, 87.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((77.24pt, 87.19pt), text(size: 9pt, fill: black)[d])
  circle((95.86pt, 66.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((95.86pt, 66.17pt), text(size: 9pt, fill: black)[e])
  circle((108.91pt, 41.30pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((108.91pt, 41.30pt), text(size: 9pt, fill: black)[f])
  circle((115.63pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((115.63pt, 14.04pt), text(size: 9pt, fill: black)[g])
  circle((115.63pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((115.63pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((108.91pt, -41.30pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((108.91pt, -41.30pt), text(size: 9pt, fill: black)[i])
  circle((95.86pt, -66.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((95.86pt, -66.17pt), text(size: 9pt, fill: black)[j])
  circle((77.24pt, -87.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((77.24pt, -87.19pt), text(size: 9pt, fill: black)[k])
  circle((54.13pt, -103.14pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.13pt, -103.14pt), text(size: 9pt, fill: black)[l])
  circle((27.88pt, -113.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.88pt, -113.09pt), text(size: 9pt, fill: black)[m])
  circle((-0.00pt, -116.48pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-0.00pt, -116.48pt), text(size: 9pt, fill: black)[n])
  circle((-27.88pt, -113.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.88pt, -113.09pt), text(size: 9pt, fill: black)[o])
  circle((-54.13pt, -103.14pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.13pt, -103.14pt), text(size: 9pt, fill: black)[p])
  circle((-77.24pt, -87.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-77.24pt, -87.19pt), text(size: 9pt, fill: black)[q])
  circle((-95.86pt, -66.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-95.86pt, -66.17pt), text(size: 9pt, fill: black)[r])
  circle((-108.91pt, -41.30pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-108.91pt, -41.30pt), text(size: 9pt, fill: black)[s])
  circle((-115.63pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-115.63pt, -14.04pt), text(size: 9pt, fill: black)[t])
  circle((-115.63pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-115.63pt, 14.04pt), text(size: 9pt, fill: black)[u])
  circle((-108.91pt, 41.30pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-108.91pt, 41.30pt), text(size: 9pt, fill: black)[v])
  circle((-95.86pt, 66.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-95.86pt, 66.17pt), text(size: 9pt, fill: black)[w])
  circle((-77.24pt, 87.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-77.24pt, 87.19pt), text(size: 9pt, fill: black)[x])
  circle((-54.13pt, 103.14pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.13pt, 103.14pt), text(size: 9pt, fill: black)[y])
  circle((-27.88pt, 113.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.88pt, 113.09pt), text(size: 9pt, fill: black)[z])
})]
)]),
  alt: "Six graphs. Graph S has 7 vertices. The edges are a b, b f, f g, f c, b c, b d, and d e. Graph N has 6 vertices. The edges are I j, I h, l k, and l m. The edges, I j, and l k intersect each other. Graph P has 6 vertices. The edges are s t, s r, r q, q p, and p o. Graph Z has 12 vertices. The edges are a b, a c, a d, a e, a f, a g, a h, h i, c j, e k, and k l. Graph C has 14 vertices. The edges are m n, n z, n o, o r, o p, o x, o y, p y, p x, p s, p t, p u, p q, p v, and p w. Graph L has 26 vertices. The edges are f q, f t, f s, f e, e o, e p, p z, e d, d m, m v, d n, n y, d c, c k, k u, c l, l k, c b, b i, i t, b j, j w, b a, b g, and b h.", caption: [Six Types of Trees],
)


    #examplebox("Example 2")[Identifying Types of Trees][
Each graph in  is one of the special types of trees we have been discussing. Identify the type of tree.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 101.85pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph U])
  line((0.00pt, 80.85pt), (27.65pt, 75.98pt), stroke: 0.7pt + black)
  line((0.00pt, 80.85pt), (51.97pt, 61.94pt), stroke: 0.7pt + black)
  line((0.00pt, 80.85pt), (70.02pt, 40.43pt), stroke: 0.7pt + black)
  line((70.02pt, 40.43pt), (79.62pt, 14.04pt), stroke: 0.7pt + black)
  line((70.02pt, 40.43pt), (79.62pt, -14.04pt), stroke: 0.7pt + black)
  line((70.02pt, 40.43pt), (70.02pt, -40.43pt), stroke: 0.7pt + black)
  line((70.02pt, 40.43pt), (51.97pt, -61.94pt), stroke: 0.7pt + black)
  line((27.65pt, -75.98pt), (0.00pt, -80.85pt), stroke: 0.7pt + black)
  line((27.65pt, -75.98pt), (-27.65pt, -75.98pt), stroke: 0.7pt + black)
  line((-27.65pt, -75.98pt), (-51.97pt, -61.94pt), stroke: 0.7pt + black)
  line((-27.65pt, -75.98pt), (-70.02pt, -40.43pt), stroke: 0.7pt + black)
  line((-27.65pt, -75.98pt), (-79.62pt, -14.04pt), stroke: 0.7pt + black)
  line((-79.62pt, -14.04pt), (-79.62pt, 14.04pt), stroke: 0.7pt + black)
  line((-27.65pt, -75.98pt), (-70.02pt, 40.43pt), stroke: 0.7pt + black)
  line((-70.02pt, 40.43pt), (-51.97pt, 61.94pt), stroke: 0.7pt + black)
  line((-70.02pt, 40.43pt), (-27.65pt, 75.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 80.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 80.85pt), text(size: 9pt, fill: black)[o])
  circle((27.65pt, 75.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.65pt, 75.98pt), text(size: 9pt, fill: black)[q])
  circle((51.97pt, 61.94pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((51.97pt, 61.94pt), text(size: 9pt, fill: black)[p])
  circle((70.02pt, 40.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((70.02pt, 40.43pt), text(size: 9pt, fill: black)[l])
  circle((79.62pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((79.62pt, 14.04pt), text(size: 9pt, fill: black)[n])
  circle((79.62pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((79.62pt, -14.04pt), text(size: 9pt, fill: black)[k])
  circle((70.02pt, -40.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((70.02pt, -40.43pt), text(size: 9pt, fill: black)[m])
  circle((51.97pt, -61.94pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((51.97pt, -61.94pt), text(size: 9pt, fill: black)[i])
  circle((27.65pt, -75.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.65pt, -75.98pt), text(size: 9pt, fill: black)[I])
  circle((0.00pt, -80.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -80.85pt), text(size: 9pt, fill: black)[j])
  circle((-27.65pt, -75.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.65pt, -75.98pt), text(size: 9pt, fill: black)[f])
  circle((-51.97pt, -61.94pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-51.97pt, -61.94pt), text(size: 9pt, fill: black)[g])
  circle((-70.02pt, -40.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-70.02pt, -40.43pt), text(size: 9pt, fill: black)[h])
  circle((-79.62pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-79.62pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((-79.62pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-79.62pt, 14.04pt), text(size: 9pt, fill: black)[e])
  circle((-70.02pt, 40.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-70.02pt, 40.43pt), text(size: 9pt, fill: black)[b])
  circle((-51.97pt, 61.94pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-51.97pt, 61.94pt), text(size: 9pt, fill: black)[c])
  circle((-27.65pt, 75.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.65pt, 75.98pt), text(size: 9pt, fill: black)[a])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph V])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[r])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[t])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[u])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[v])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[w])
})]
)]),
  alt: "Two graphs. Graph U has 17 vertices. The edges are o q, o p, o l, l n, l k, l m, l i, I j, I f, f g, f h, f d, d e, f b, b c, and b a. Graph V hs 6 vertices. The edges are r s, s t, t u, u v, and v w. The edges, s t and u v intersect.", caption: [Graphs #emph[U] and #emph[V]],
)


      
      #solutionbox[
Graph #emph[U] has a central path #emph[a] → #emph[b] → #emph[d] → #emph[f] → #emph[i] → #emph[l] → #emph[o] → #emph[q]. Each vertex that is not on the path has degree 1 and is adjacent to a vertex that is on the path. So, #emph[U] is a caterpillar tree.


        Graph #emph[V] is a path graph because it is a single path connecting exactly two vertices of degree one, #emph[r] → #emph[s] → #emph[u] → #emph[v] → #emph[w].
]
]


    
  
  
    
=== Characteristics of Trees


    As we study trees, it is helpful to be familiar with some of their characteristics. For example, if you add an edge to a tree graph between any two existing vertices, you will create a cycle, and the resulting graph is no longer a tree. Some examples are shown. Adding edge #emph[bj] to Graph #emph[T] creates cycle (#emph[b], #emph[c], #emph[i], #emph[j]). Adding edge #emph[rt] to Graph #emph[P] creates cycle (#emph[r], #emph[s], #emph[t]). Adding edge #emph[tv] to Graph #emph[S] creates cycle (#emph[t], #emph[u], #emph[v]).


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 88.53pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, 67.53pt), (27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (-14.04pt, -66.05pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-14.04pt, -66.05pt), (-39.69pt, -54.63pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-39.69pt, -54.63pt), (-58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((-58.48pt, -33.76pt), (-27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (-67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((58.48pt, -33.76pt), (39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((39.69pt, -54.63pt), (14.04pt, -66.05pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (-39.69pt, -54.63pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 67.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.53pt), text(size: 9pt, fill: black)[a])
  circle((27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.47pt, 61.69pt), text(size: 9pt, fill: black)[b])
  circle((50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.18pt, 45.19pt), text(size: 9pt, fill: black)[c])
  circle((64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.22pt, 20.87pt), text(size: 9pt, fill: black)[d])
  circle((67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((67.16pt, -7.06pt), text(size: 9pt, fill: black)[e])
  circle((58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.48pt, -33.76pt), text(size: 9pt, fill: black)[f])
  circle((39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.69pt, -54.63pt), text(size: 9pt, fill: black)[g])
  circle((14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -66.05pt), text(size: 9pt, fill: black)[h])
  circle((-14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -66.05pt), text(size: 9pt, fill: black)[i])
  circle((-39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.69pt, -54.63pt), text(size: 9pt, fill: black)[j])
  circle((-58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.48pt, -33.76pt), text(size: 9pt, fill: black)[k])
  circle((-67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-67.16pt, -7.06pt), text(size: 9pt, fill: black)[l])
  circle((-64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.22pt, 20.87pt), text(size: 9pt, fill: black)[m])
  circle((-50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-50.18pt, 45.19pt), text(size: 9pt, fill: black)[n])
  circle((-27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.47pt, 61.69pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph S])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, 42.00pt), (40.95pt, -9.35pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, 42.00pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (40.95pt, -9.35pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[u])
  circle((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[t])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[v])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[w])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[x])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[y])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[z])
})]
)]),
  alt: "Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. The edges, c i, and i j are in blue. A dashed edge connects b and j. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. The edges, t s, and s r are in blue. A dashed edge connects t and r. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. The edges, u t, and u v are in blue. A dashed edge connects t and v.", caption: [Adding Edges to Trees],
)


    It is also true that removing an edge from a tree graph will increase the number of components and the graph will no longer be connected. In fact, you can see in  that removing one or more edges can create a forest. Removing edge #emph[qr] from Graph #emph[P] creates a graph with two components, one with vertices #emph[o, p] and #emph[q], and the other with vertices #emph[r, s], and #emph[t]. Removing edge #emph[uw] from Graph #emph[S] creates two components, one with just vertex #emph[w] and the other with the rest of the vertices. When two edges were removed from Graph #emph[T], edge #emph[bf] and edge #emph[cd], creates a graph with three components as shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 88.53pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, 67.53pt), (27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (64.22pt, 20.87pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((50.18pt, 45.19pt), (-14.04pt, -66.05pt), stroke: 0.7pt + black)
  line((-14.04pt, -66.05pt), (-39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((-39.69pt, -54.63pt), (-58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((-58.48pt, -33.76pt), (-27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (-67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (58.48pt, -33.76pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((58.48pt, -33.76pt), (39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((39.69pt, -54.63pt), (14.04pt, -66.05pt), stroke: 0.7pt + black)
  circle((0.00pt, 67.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.53pt), text(size: 9pt, fill: black)[a])
  circle((27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.47pt, 61.69pt), text(size: 9pt, fill: black)[b])
  circle((50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.18pt, 45.19pt), text(size: 9pt, fill: black)[c])
  circle((64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.22pt, 20.87pt), text(size: 9pt, fill: black)[d])
  circle((67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((67.16pt, -7.06pt), text(size: 9pt, fill: black)[e])
  circle((58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.48pt, -33.76pt), text(size: 9pt, fill: black)[f])
  circle((39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.69pt, -54.63pt), text(size: 9pt, fill: black)[g])
  circle((14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -66.05pt), text(size: 9pt, fill: black)[h])
  circle((-14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -66.05pt), text(size: 9pt, fill: black)[i])
  circle((-39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.69pt, -54.63pt), text(size: 9pt, fill: black)[j])
  circle((-58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.48pt, -33.76pt), text(size: 9pt, fill: black)[k])
  circle((-67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-67.16pt, -7.06pt), text(size: 9pt, fill: black)[l])
  circle((-64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.22pt, 20.87pt), text(size: 9pt, fill: black)[m])
  circle((-50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-50.18pt, 45.19pt), text(size: 9pt, fill: black)[n])
  circle((-27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.47pt, 61.69pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  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: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph S])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (18.22pt, -37.84pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-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)[u])
  circle((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[t])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[v])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[w])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[x])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[y])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[z])
})]
)]),
  alt: "Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. The edges, d c, and b f are in dashed lines. The graph is separated into three blocks. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. The edge, q r is in dashed lines. The graph is separated into two blocks. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. The edge, u w is in dashed lines. The graph is separated into two blocks.", caption: [Removing Edges from Trees],
)


    A very useful characteristic of tree graphs is that the number of edges is always one less than the number of vertices. In fact, any connected graph in which the number of edges is one less than the number of vertices is guaranteed to be a tree. Some examples are given in .


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 88.53pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, 67.53pt), (27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((50.18pt, 45.19pt), (-14.04pt, -66.05pt), stroke: 0.7pt + black)
  line((-14.04pt, -66.05pt), (-39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((-39.69pt, -54.63pt), (-58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((-58.48pt, -33.76pt), (-27.47pt, 61.69pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((64.22pt, 20.87pt), (-67.16pt, -7.06pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-50.18pt, 45.19pt), stroke: 0.7pt + black)
  line((67.16pt, -7.06pt), (-64.22pt, 20.87pt), stroke: 0.7pt + black)
  line((27.47pt, 61.69pt), (58.48pt, -33.76pt), stroke: 0.7pt + black)
  line((58.48pt, -33.76pt), (39.69pt, -54.63pt), stroke: 0.7pt + black)
  line((39.69pt, -54.63pt), (14.04pt, -66.05pt), stroke: 0.7pt + black)
  circle((0.00pt, 67.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.53pt), text(size: 9pt, fill: black)[a])
  circle((27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.47pt, 61.69pt), text(size: 9pt, fill: black)[b])
  circle((50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.18pt, 45.19pt), text(size: 9pt, fill: black)[c])
  circle((64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.22pt, 20.87pt), text(size: 9pt, fill: black)[d])
  circle((67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((67.16pt, -7.06pt), text(size: 9pt, fill: black)[e])
  circle((58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.48pt, -33.76pt), text(size: 9pt, fill: black)[f])
  circle((39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.69pt, -54.63pt), text(size: 9pt, fill: black)[g])
  circle((14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -66.05pt), text(size: 9pt, fill: black)[h])
  circle((-14.04pt, -66.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -66.05pt), text(size: 9pt, fill: black)[i])
  circle((-39.69pt, -54.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.69pt, -54.63pt), text(size: 9pt, fill: black)[j])
  circle((-58.48pt, -33.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.48pt, -33.76pt), text(size: 9pt, fill: black)[k])
  circle((-67.16pt, -7.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-67.16pt, -7.06pt), text(size: 9pt, fill: black)[l])
  circle((-64.22pt, 20.87pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.22pt, 20.87pt), text(size: 9pt, fill: black)[m])
  circle((-50.18pt, 45.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-50.18pt, 45.19pt), text(size: 9pt, fill: black)[n])
  circle((-27.47pt, 61.69pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.47pt, 61.69pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph P])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[t])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[s])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[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)[q])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[o])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph S])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-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)[u])
  circle((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[t])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[v])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[w])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[x])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[y])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[z])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph Z])
  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((0.00pt, 54.25pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, 54.25pt), (-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), (-54.25pt, -0.00pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (-46.98pt, 27.12pt), 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)[a])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), text(size: 9pt, fill: black)[b])
  circle((46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, 27.12pt), text(size: 9pt, fill: black)[c])
  circle((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[d])
  circle((46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((46.98pt, -27.12pt), text(size: 9pt, fill: black)[e])
  circle((27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, -46.98pt), text(size: 9pt, fill: black)[f])
  circle((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[g])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[h])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[i])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[j])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[k])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[l])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 84.10pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph C])
  line((0.00pt, 63.10pt), (27.38pt, 56.85pt), stroke: 0.7pt + black)
  line((27.38pt, 56.85pt), (49.33pt, 39.34pt), stroke: 0.7pt + black)
  line((27.38pt, 56.85pt), (61.51pt, 14.04pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (61.51pt, -14.04pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (49.33pt, -39.34pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (27.38pt, -56.85pt), stroke: 0.7pt + black)
  line((61.51pt, 14.04pt), (0.00pt, -63.10pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (0.00pt, -63.10pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (27.38pt, -56.85pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-27.38pt, -56.85pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-49.33pt, -39.34pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-61.51pt, -14.04pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-61.51pt, 14.04pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-49.33pt, 39.34pt), stroke: 0.7pt + black)
  line((49.33pt, -39.34pt), (-27.38pt, 56.85pt), stroke: 0.7pt + black)
  circle((0.00pt, 63.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 63.10pt), text(size: 9pt, fill: black)[m])
  circle((27.38pt, 56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.38pt, 56.85pt), text(size: 9pt, fill: black)[n])
  circle((49.33pt, 39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, 39.34pt), text(size: 9pt, fill: black)[z])
  circle((61.51pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((61.51pt, 14.04pt), text(size: 9pt, fill: black)[o])
  circle((61.51pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((61.51pt, -14.04pt), text(size: 9pt, fill: black)[r])
  circle((49.33pt, -39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -39.34pt), text(size: 9pt, fill: black)[p])
  circle((27.38pt, -56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.38pt, -56.85pt), text(size: 9pt, fill: black)[x])
  circle((0.00pt, -63.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -63.10pt), text(size: 9pt, fill: black)[y])
  circle((-27.38pt, -56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.38pt, -56.85pt), text(size: 9pt, fill: black)[s])
  circle((-49.33pt, -39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -39.34pt), text(size: 9pt, fill: black)[t])
  circle((-61.51pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-61.51pt, -14.04pt), text(size: 9pt, fill: black)[u])
  circle((-61.51pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-61.51pt, 14.04pt), text(size: 9pt, fill: black)[q])
  circle((-49.33pt, 39.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, 39.34pt), text(size: 9pt, fill: black)[v])
  circle((-27.38pt, 56.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.38pt, 56.85pt), text(size: 9pt, fill: black)[w])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 128.56pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph L])
  line((0.00pt, 107.56pt), (27.84pt, 103.90pt), stroke: 0.7pt + black)
  line((0.00pt, 107.56pt), (53.78pt, 93.15pt), stroke: 0.7pt + black)
  line((0.00pt, 107.56pt), (76.06pt, 76.06pt), stroke: 0.7pt + black)
  line((0.00pt, 107.56pt), (93.15pt, 53.78pt), stroke: 0.7pt + black)
  line((93.15pt, 53.78pt), (103.90pt, 27.84pt), stroke: 0.7pt + black)
  line((93.15pt, 53.78pt), (107.56pt, 0.00pt), stroke: 0.7pt + black)
  line((107.56pt, 0.00pt), (103.90pt, -27.84pt), stroke: 0.7pt + black)
  line((93.15pt, 53.78pt), (93.15pt, -53.78pt), stroke: 0.7pt + black)
  line((93.15pt, -53.78pt), (76.06pt, -76.06pt), stroke: 0.7pt + black)
  line((76.06pt, -76.06pt), (53.78pt, -93.15pt), stroke: 0.7pt + black)
  line((93.15pt, -53.78pt), (27.84pt, -103.90pt), stroke: 0.7pt + black)
  line((27.84pt, -103.90pt), (0.00pt, -107.56pt), stroke: 0.7pt + black)
  line((93.15pt, -53.78pt), (-27.84pt, -103.90pt), stroke: 0.7pt + black)
  line((-27.84pt, -103.90pt), (-53.78pt, -93.15pt), stroke: 0.7pt + black)
  line((-53.78pt, -93.15pt), (-76.06pt, -76.06pt), stroke: 0.7pt + black)
  line((-27.84pt, -103.90pt), (-93.15pt, -53.78pt), stroke: 0.7pt + black)
  line((-93.15pt, -53.78pt), (-53.78pt, -93.15pt), stroke: 0.7pt + black)
  line((-27.84pt, -103.90pt), (-103.90pt, -27.84pt), stroke: 0.7pt + black)
  line((-103.90pt, -27.84pt), (-107.56pt, -0.00pt), stroke: 0.7pt + black)
  line((-107.56pt, -0.00pt), (53.78pt, 93.15pt), stroke: 0.7pt + black)
  line((-103.90pt, -27.84pt), (-103.90pt, 27.84pt), stroke: 0.7pt + black)
  line((-103.90pt, 27.84pt), (-93.15pt, 53.78pt), stroke: 0.7pt + black)
  line((-103.90pt, -27.84pt), (-76.06pt, 76.06pt), stroke: 0.7pt + black)
  line((-103.90pt, -27.84pt), (-53.78pt, 93.15pt), stroke: 0.7pt + black)
  line((-103.90pt, -27.84pt), (-27.84pt, 103.90pt), stroke: 0.7pt + black)
  circle((0.00pt, 107.56pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 107.56pt), text(size: 9pt, fill: black)[f])
  circle((27.84pt, 103.90pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.84pt, 103.90pt), text(size: 9pt, fill: black)[q])
  circle((53.78pt, 93.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((53.78pt, 93.15pt), text(size: 9pt, fill: black)[t])
  circle((76.06pt, 76.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((76.06pt, 76.06pt), text(size: 9pt, fill: black)[s])
  circle((93.15pt, 53.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((93.15pt, 53.78pt), text(size: 9pt, fill: black)[e])
  circle((103.90pt, 27.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((103.90pt, 27.84pt), text(size: 9pt, fill: black)[o])
  circle((107.56pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((107.56pt, 0.00pt), text(size: 9pt, fill: black)[p])
  circle((103.90pt, -27.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((103.90pt, -27.84pt), text(size: 9pt, fill: black)[z])
  circle((93.15pt, -53.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((93.15pt, -53.78pt), text(size: 9pt, fill: black)[d])
  circle((76.06pt, -76.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((76.06pt, -76.06pt), text(size: 9pt, fill: black)[m])
  circle((53.78pt, -93.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((53.78pt, -93.15pt), text(size: 9pt, fill: black)[v])
  circle((27.84pt, -103.90pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.84pt, -103.90pt), text(size: 9pt, fill: black)[n])
  circle((0.00pt, -107.56pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -107.56pt), text(size: 9pt, fill: black)[y])
  circle((-27.84pt, -103.90pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.84pt, -103.90pt), text(size: 9pt, fill: black)[c])
  circle((-53.78pt, -93.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-53.78pt, -93.15pt), text(size: 9pt, fill: black)[k])
  circle((-76.06pt, -76.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-76.06pt, -76.06pt), text(size: 9pt, fill: black)[u])
  circle((-93.15pt, -53.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-93.15pt, -53.78pt), text(size: 9pt, fill: black)[l])
  circle((-103.90pt, -27.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-103.90pt, -27.84pt), text(size: 9pt, fill: black)[b])
  circle((-107.56pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-107.56pt, -0.00pt), text(size: 9pt, fill: black)[i])
  circle((-103.90pt, 27.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-103.90pt, 27.84pt), text(size: 9pt, fill: black)[j])
  circle((-93.15pt, 53.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-93.15pt, 53.78pt), text(size: 9pt, fill: black)[w])
  circle((-76.06pt, 76.06pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-76.06pt, 76.06pt), text(size: 9pt, fill: black)[a])
  circle((-53.78pt, 93.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-53.78pt, 93.15pt), text(size: 9pt, fill: black)[g])
  circle((-27.84pt, 103.90pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.84pt, 103.90pt), text(size: 9pt, fill: black)[h])
})]
)]),
  alt: "Six graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. Graph Z has 12 vertices. The edges are a b, a c, a d, a e, a f, a g, a h, h i, c j, e k, and k l. Graph C has 14 vertices. The edges are m n, n z, n o, o r, o p, o x, o y, p y, p x, p s, p t, p u, p q, p v, and p w. Graph L has 26 vertices. The edges are f q, f t, f s, f e, e o, e p, p z, e d, d m, m v, d n, n y, d c, c k, k u, c l, l k, c b, b i, i t, b j, j w, b a, b g, and b h.", caption: [Number of Vertices and Edges in Trees vs. Other Graphs],
)


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
The number of edges in a tree graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "n minus 1")[$n − 1$].


      A connected graph with n vertices and #math.equation(block: false, alt: "n minus 1")[$n − 1$] edges is a tree graph.
]


    #examplebox("Example 3")[Exploring Characteristics of Trees][
Use Graphs #emph[I] and #emph[J] in  to answer each question.


        #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 I])
  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((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)
  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 J])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (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), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (-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)[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)[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)[i])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[j])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[k])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[l])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[m])
})]
)]),
  alt: "Two graphs. Graph I has six vertices: a, b, c, d, e, and f. Edges connect a b, b c, b e, d e, and e f. Graph J has seven vertices: g h, i, j, k, l, and m. Edges connect g h, h i, j h, j l, k l, and l m.", caption: [Graphs #emph[I] and #emph[J]],
)


        + Which vertices are in each of the components that remain when edge #emph[be] is removed from Graph #emph[I]?
+ Determine the number of edges and the number of vertices in Graph #emph[J]. Explain how this confirms that Graph #emph[J] is a tree.
+ What kind of cycle is created if edge #emph[im] is added to Graph #emph[J]?


      
      #solutionbox[
+ When edge #emph[be] is removed, there are two components that remain. One component includes vertices #emph[a, b], and #emph[c]. The other component includes vertices #emph[d, e], and #emph[f].
+ There are seven vertices and six edges in Graph #emph[J]. This confirms that Graph #emph[J] is a tree because the number of edges is one less than the number of vertices.
+ The pentagon (#emph[i], #emph[h], #emph[j], #emph[l], #emph[m]) is created when edge #emph[im] is added to Graph #emph[J].
]
]


    
    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Graph Theory in the Movies]


      In the 1997 film #emph[Good Will Hunting], the main character, Will, played by Matt Damon, solves what is supposed to be an exceptionally difficult graph theory problem, “Draw all the homeomorphically irreducible trees of size #math.equation(block: false, alt: "n equals 10")[$n = 10$].” That sounds terrifying! But don’t panic. Watch this great Numberphile video to see why this is actually a problem you can do at home!
]


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Hunting_Numberphile")[The Problem in #emph[Good Will Hunting] by Numberphile]
]


  
  
    
=== Spanning Trees


    Suppose that you planned to set up your own computer network with four devices. One option is to use a “mesh topology” like the one in , in which each device is connected directly to every other device in the network.


    #figure(figph[Four illustrations represent the common network configurations. The first illustration represents mesh topology. Six computers are interconnected. The second illustration represents a ring topology. Five computers are connected in a ring. The third illustration represents star topology. A computer at the center is connected to five computers surrounding it. The fourth illustration represents tree topology. Two branches arise from a horizontal bus. Each branch has a computer at the center connected to five computers surrounding it.], alt: "Four illustrations represent the common network configurations. The first illustration represents mesh topology. Six computers are interconnected. The second illustration represents a ring topology. Five computers are connected in a ring. The third illustration represents star topology. A computer at the center is connected to five computers surrounding it. The fourth illustration represents tree topology. Two branches arise from a horizontal bus. Each branch has a computer at the center connected to five computers surrounding it.", caption: [Common Network Configurations])


    The mesh topology for four devices could be represented by the complete Graph #emph[A]#sub[1] in  where the vertices represent the devices, and the edges represent network connections. However, the devices could be networked using fewer connections. Graphs #emph[A]#sub[2], #emph[A]#sub[3,] and #emph[A]#sub[4] of  show configurations in which three of the six edges have been removed. Each of the Graphs #emph[A]#sub[2], #emph[A]#sub[3] and #emph[A]#sub[4] in  is a tree because it is connected and contains no cycles. Since Graphs #emph[A]#sub[2], #emph[A]#sub[3] and #emph[A]#sub[4] are also subgraphs of Graph #emph[A]#sub[1] that include every vertex of the original graph, they are also known as #strong[spanning trees].


    #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 A 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)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 2])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 3])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 4])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.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: "Four graphs. Graph A 1 has four vertices: a, b, c, and d. The edges are a b, b d, d c, c a, a d, and b c. Graph A 2 has four vertices: a, b, c, and d. The edges are a b, b c, and c d. Graph A 3 has four vertices: a, b, c, and d. The edges are a b, a c, and c d. Graph A 4 has four vertices: a, b, c, and d. The edges are a b, a c, and a d.", caption: [Network Configurations for Four Devices],
)


    By definition, spanning trees must span the whole graph by visiting all the vertices. Since spanning trees are subgraphs, they may only have edges between vertices that were adjacent in the original graph. Since spanning trees are trees, they are connected and they are acyclic. So, when deciding whether a graph is a spanning tree, check the following characteristics:


    - All vertices are included.
- No vertices are adjacent that were not adjacent in the original graph.
- The graph is connected.
- There are no cycles.


    #examplebox("Example 4")[Identifying Spanning Trees][
Use  to determine which of graphs #emph[M]#sub[1], #emph[M]#sub[2], #emph[M]#sub[3], and #emph[M]#sub[4], are spanning trees of #emph[Q].


        #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 Q])
  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((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.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), (-36.37pt, 21.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((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 M 1])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[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 M 2])
  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)
  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 M 3])
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((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)
  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 M 4])
  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)
  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])
})]
)]),
  alt: "Five graphs. Graph Q has six vertices: a, b, c, d, e, and f. The edges are a b, a c, a d, b d, d f, c d, c e, c f, and e f. Graph M 1 has six vertices: a, b, c, d, e, and f. The edges are a b, b d, d c, c e, f, and f d. Graph M 2 has six vertices: a, b, c, d, e, and f. The edges are a b, a d, d f, f e, and e c. Graph M 3 has six vertices; a, b, c, d, e, and f. The edges are b d, d f, a f, f e, and e c. Graph M 4 has six vertices: a, b, c, d, e, and f. The edges are a b, c e, e f, and f d.", caption: [Graphs #emph[Q], #emph[M]#sub[1], #emph[M]#sub[2], #emph[M]#sub[3,] and #emph[M]#sub[4]],
)


      
      #solutionbox[
+ Graph #emph[M]#sub[1] is not a spanning tree of Graph #emph[Q] because it has a cycle (#emph[c], #emph[d], #emph[f], #emph[e]).
+ Graph #emph[M]#sub[2] is a spanning tree of Graph #emph[Q] because it has all the original vertices, no vertices are adjacent in #emph[M]#sub[2] that weren’t adjacent in Graph #emph[Q], Graph #emph[M]#sub[2] is connected and it contains no cycles.
+ Graph #emph[M]#sub[3] is not a spanning tree of Graph #emph[Q] because vertices #emph[a] and #emph[f] are adjacent in Graph #emph[M]#sub[3] but not in Graph #emph[Q].
+ Graph #emph[M]#sub[4] is not a spanning tree of Graph #emph[Q] because it is not connected.


        So, only graph #emph[M]#sub[2] is a spanning tree of Graph #emph[Q].
]
]


    
  
  
    
=== Constructing a Spanning Tree Using Paths


    Suppose that you wanted to find a spanning tree within a graph. One approach is to find paths within the graph. You can start at any vertex, go any direction, and create a path through the graph stopping only when you can’t continue without backtracking as shown.


    #figure(figph[A graph with 23 vertices and 35 edges. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.], alt: "A graph with 23 vertices and 35 edges. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.", caption: [First Phase to Construct a Spanning Tree])


    Once you have stopped, pick a vertex along the path you drew as a starting point for another path. Make sure to visit only vertices you have not visited before as shown.


    #figure(figph[A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.], alt: "A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.", caption: [Intermediate Phase to Construct a Spanning Tree])


    Repeat this process until all vertices have been visited as shown.


    #figure(figph[A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here. Two edges are highlighted in purple.], alt: "A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here. Two edges are highlighted in purple.", caption: [Final Phase to Construct a Spanning Tree])


    The end result is a tree that spans the entire graph as shown.


    #figure(figph[A graph with 23 vertices and 22 edges.], alt: "A graph with 23 vertices and 22 edges.", caption: [The Resulting Spanning Tree])


    Notice that this subgraph is a tree because it is connected and acyclic. It also visits every vertex of the original graph, so it is a spanning tree. However, it is not the only spanning tree for this graph. By making different turns, we could create any number of distinct spanning trees.


    #examplebox("Example 5")[Constructing Spanning Trees][
Construct two distinct spanning trees for the graph in .


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 134.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[Graph L])
  line((20.00pt, 20.00pt), (60.00pt, 20.00pt), (60.00pt, 60.00pt), (20.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((20.00pt, 60.00pt), (60.00pt, 60.00pt), (40.00pt, 100.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((140.00pt, 20.00pt), (180.00pt, 20.00pt), (180.00pt, 60.00pt), (140.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((140.00pt, 60.00pt), (180.00pt, 60.00pt), (160.00pt, 100.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((60.00pt, 60.00pt), (80.00pt, 80.00pt), (120.00pt, 80.00pt), (140.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((20.00pt, 20.00pt), (60.00pt, 60.00pt), stroke: 0.7pt + black)
  line((140.00pt, 20.00pt), (180.00pt, 60.00pt), stroke: 0.7pt + black)
})]),
  alt: "Graph L has 11 vertices and 19 edges. The graph resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines.", caption: [Graph #emph[L]],
)


      
      #solutionbox[
Two possible solutions are given in  and .


        #figure(figph[Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.], alt: "Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.", caption: [First Spanning Tree for Graph #emph[L]])


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 77.66pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph L])
  line((0.00pt, 55.16pt), (29.82pt, 46.40pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((29.82pt, 46.40pt), (50.17pt, 22.91pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((50.17pt, 22.91pt), (54.60pt, -7.85pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((54.60pt, -7.85pt), (41.69pt, -36.12pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((41.69pt, -36.12pt), (15.54pt, -52.92pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((15.54pt, -52.92pt), (-15.54pt, -52.92pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((-15.54pt, -52.92pt), (-41.69pt, -36.12pt), stroke: (paint: rgb("#800080"), thickness: 0.7pt))
  line((-41.69pt, -36.12pt), (-54.60pt, -7.85pt), stroke: (paint: rgb("#800080"), thickness: 0.7pt))
  line((-54.60pt, -7.85pt), (-50.17pt, 22.91pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-50.17pt, 22.91pt), (-29.82pt, 46.40pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, 55.16pt), (50.17pt, 22.91pt), stroke: 0.7pt + black)
  line((29.82pt, 46.40pt), (54.60pt, -7.85pt), stroke: 0.7pt + black)
  line((50.17pt, 22.91pt), (41.69pt, -36.12pt), stroke: 0.7pt + black)
  line((54.60pt, -7.85pt), (15.54pt, -52.92pt), stroke: 0.7pt + black)
  line((41.69pt, -36.12pt), (-15.54pt, -52.92pt), stroke: 0.7pt + black)
  line((15.54pt, -52.92pt), (-41.69pt, -36.12pt), stroke: 0.7pt + black)
  line((-15.54pt, -52.92pt), (-54.60pt, -7.85pt), stroke: 0.7pt + black)
  line((-41.69pt, -36.12pt), (-50.17pt, 22.91pt), stroke: 0.7pt + black)
  line((-54.60pt, -7.85pt), (-29.82pt, 46.40pt), stroke: 0.7pt + black)
  circle((0.00pt, 55.16pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 55.16pt), text(size: 9pt, fill: black)[v1])
  circle((29.82pt, 46.40pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.82pt, 46.40pt), text(size: 9pt, fill: black)[v2])
  circle((50.17pt, 22.91pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.17pt, 22.91pt), text(size: 9pt, fill: black)[v3])
  circle((54.60pt, -7.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.60pt, -7.85pt), text(size: 9pt, fill: black)[v4])
  circle((41.69pt, -36.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.69pt, -36.12pt), text(size: 9pt, fill: black)[v5])
  circle((15.54pt, -52.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((15.54pt, -52.92pt), text(size: 9pt, fill: black)[v6])
  circle((-15.54pt, -52.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-15.54pt, -52.92pt), text(size: 9pt, fill: black)[v7])
  circle((-41.69pt, -36.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.69pt, -36.12pt), text(size: 9pt, fill: black)[v8])
  circle((-54.60pt, -7.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.60pt, -7.85pt), text(size: 9pt, fill: black)[v9])
  circle((-50.17pt, 22.91pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-50.17pt, 22.91pt), text(size: 9pt, fill: black)[v10])
  circle((-29.82pt, 46.40pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-29.82pt, 46.40pt), text(size: 9pt, fill: black)[v11])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 77.66pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Final Tree])
  line((0.00pt, 55.16pt), (29.82pt, 46.40pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((29.82pt, 46.40pt), (50.17pt, 22.91pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((50.17pt, 22.91pt), (54.60pt, -7.85pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((54.60pt, -7.85pt), (41.69pt, -36.12pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((41.69pt, -36.12pt), (15.54pt, -52.92pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((15.54pt, -52.92pt), (-15.54pt, -52.92pt), stroke: (paint: rgb("#00874a"), thickness: 0.7pt))
  line((-15.54pt, -52.92pt), (-41.69pt, -36.12pt), stroke: (paint: rgb("#800080"), thickness: 0.7pt))
  line((-41.69pt, -36.12pt), (-54.60pt, -7.85pt), stroke: (paint: rgb("#800080"), thickness: 0.7pt))
  line((-54.60pt, -7.85pt), (-50.17pt, 22.91pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-50.17pt, 22.91pt), (-29.82pt, 46.40pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  circle((0.00pt, 55.16pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 55.16pt), text(size: 9pt, fill: black)[v1])
  circle((29.82pt, 46.40pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.82pt, 46.40pt), text(size: 9pt, fill: black)[v2])
  circle((50.17pt, 22.91pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((50.17pt, 22.91pt), text(size: 9pt, fill: black)[v3])
  circle((54.60pt, -7.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.60pt, -7.85pt), text(size: 9pt, fill: black)[v4])
  circle((41.69pt, -36.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.69pt, -36.12pt), text(size: 9pt, fill: black)[v5])
  circle((15.54pt, -52.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((15.54pt, -52.92pt), text(size: 9pt, fill: black)[v6])
  circle((-15.54pt, -52.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-15.54pt, -52.92pt), text(size: 9pt, fill: black)[v7])
  circle((-41.69pt, -36.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.69pt, -36.12pt), text(size: 9pt, fill: black)[v8])
  circle((-54.60pt, -7.85pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.60pt, -7.85pt), text(size: 9pt, fill: black)[v9])
  circle((-50.17pt, 22.91pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-50.17pt, 22.91pt), text(size: 9pt, fill: black)[v10])
  circle((-29.82pt, 46.40pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-29.82pt, 46.40pt), text(size: 9pt, fill: black)[v11])
})]
)]),
  alt: "Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.", caption: [Second Spanning Tree for Graph #emph[L]],
)
]
]


    
  
  
    
=== Revealing Spanning Trees


    Another approach to finding a spanning tree in a connected graph involves removing unwanted edges to reveal a spanning tree. Consider Graph #emph[D] in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 66.43pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph D])
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[a])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[b])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[c])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[e])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[f])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[g])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[i])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[j])
})]),
  alt: "Graph D has 10 vertices. The vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and I j.", caption: [Graph #emph[D]],
)


    Graph #emph[D] has 10 vertices. A spanning tree of Graph #emph[D] must have 9 edges, because the number of edges is one less than the number of vertices in any tree. Graph #emph[D] has 13 edges so 4 need to be removed. To determine which 4 edges to remove, remember that trees do not have cycles. There are four triangles in Graph #emph[D] that we need to break up. We can accomplish this by removing 1 edge from each of the triangles. There are many ways this can be done. Two of these ways are shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (0.00pt, 45.43pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((43.21pt, -14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((26.71pt, 36.76pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-26.71pt, 36.76pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[a])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[b])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[c])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[e])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[f])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[g])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[i])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[a])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[b])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[c])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[e])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[f])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[g])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[i])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (0.00pt, 45.43pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((43.21pt, -14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-26.71pt, -36.76pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 45.43pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (0.00pt, -45.43pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-43.21pt, 14.04pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((26.71pt, 36.76pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[a])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[b])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[c])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[e])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[f])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[g])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[i])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[a])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[b])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[c])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[d])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[e])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[f])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[g])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[h])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[i])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[j])
})]
)]),
  alt: "Four graphs depict removing edges from graph D. In the first graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, e f, g h, and b j are shown in dashed lines. The second graph is the same as that of the first with edges, a c, e f, g h, and b j removed. In the third graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, a g, b f, and b i are shown in dashed lines. The fourth graph is the same as that of the first with edges, a c, a g, b f, and b i removed.", caption: [Removing Four Edges from Graph #emph[D]],
)


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Spanning_Trees_in_Graph_Theory")[Spanning Trees in Graph Theory]
]


    #examplebox("Example 6")[Removing Edges to Find Spanning Trees][
Use the graph in  to answer each question.


        #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 V])
  line((-14.36pt, -39.47pt), (41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((-14.36pt, -39.47pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (27.00pt, 32.17pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (14.36pt, -39.47pt), stroke: 0.7pt + black)
  line((14.36pt, -39.47pt), (-41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((-41.36pt, 7.29pt), (-27.00pt, 32.17pt), stroke: 0.7pt + black)
  line((-27.00pt, 32.17pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (27.00pt, 32.17pt), 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((27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.00pt, 32.17pt), text(size: 9pt, fill: black)[b])
  circle((41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.36pt, 7.29pt), text(size: 9pt, fill: black)[c])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[d])
  circle((14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.36pt, -39.47pt), text(size: 9pt, fill: black)[e])
  circle((-14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.36pt, -39.47pt), text(size: 9pt, fill: black)[f])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[g])
  circle((-41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.36pt, 7.29pt), text(size: 9pt, fill: black)[h])
  circle((-27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.00pt, 32.17pt), text(size: 9pt, fill: black)[i])
})]),
  alt: "Graph V has 9 vertices. The vertices are labeled from a to i. The edges are f c, f a, c a, c d, d a, a b, b e, e h, h i, I g, and g b.", caption: [Graph #emph[V]],
)


        + Determine the number of edges that must be removed to reveal a spanning tree.
+ Name all the undirected cycles in Graph #emph[V].
+ Find two distinct spanning trees of Graph #emph[V].


      
      #solutionbox[
+ Graph #emph[V] has nine vertices so a spanning tree for the graph must have 8 edges. Since Graph #emph[V] has 11 edges, 3 edges must be removed to reveal a spanning tree.
+ (#emph[a], #emph[c], #emph[d]), (#emph[a], #emph[c], #emph[f]), (#emph[a], #emph[d], #emph[c], #emph[f]), and (#emph[b], #emph[e], #emph[h], #emph[i], #emph[g])
+ To find the first spanning tree, remove edge #emph[ac], which will break up both of the triangles, remove edge #emph[cf], which will break up the quadrilateral, and remove #emph[be], which will break up the pentagon, to give us the spanning tree shown.
    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-14.36pt, -39.47pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (27.00pt, 32.17pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-27.00pt, 32.17pt), stroke: 0.7pt + black)
  line((-27.00pt, 32.17pt), (-41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((-41.36pt, 7.29pt), (14.36pt, -39.47pt), 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((27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.00pt, 32.17pt), text(size: 9pt, fill: black)[b])
  circle((41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.36pt, 7.29pt), text(size: 9pt, fill: black)[c])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[d])
  circle((14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.36pt, -39.47pt), text(size: 9pt, fill: black)[e])
  circle((-14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.36pt, -39.47pt), text(size: 9pt, fill: black)[f])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[g])
  circle((-41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.36pt, 7.29pt), text(size: 9pt, fill: black)[h])
  circle((-27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.00pt, 32.17pt), text(size: 9pt, fill: black)[i])
})]),
  alt: "A graph has 9 vertices. The vertices are labeled from a to i. The edges are f a, c d, d a, a b, b g, g i, I h, and h e.", caption: [Spanning Tree Formed Removing #emph[ac, cf], and #emph[be]],
)

To find another spanning tree, remove #emph[ad], which will break up (#emph[a], #emph[c], #emph[d]) and (#emph[a], #emph[d], #emph[c], #emph[f]), remove #emph[af] to break up (#emph[a], #emph[c], #emph[f]), and remove #emph[hi] to break up (#emph[b], #emph[e], #emph[h], #emph[i], #emph[g]). This will give us the spanning tree in .

#figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-14.36pt, -39.47pt), (41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (27.00pt, 32.17pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (14.36pt, -39.47pt), stroke: 0.7pt + black)
  line((14.36pt, -39.47pt), (-41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-27.00pt, 32.17pt), 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((27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.00pt, 32.17pt), text(size: 9pt, fill: black)[b])
  circle((41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.36pt, 7.29pt), text(size: 9pt, fill: black)[c])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[d])
  circle((14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.36pt, -39.47pt), text(size: 9pt, fill: black)[e])
  circle((-14.36pt, -39.47pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.36pt, -39.47pt), text(size: 9pt, fill: black)[f])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[g])
  circle((-41.36pt, 7.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.36pt, 7.29pt), text(size: 9pt, fill: black)[h])
  circle((-27.00pt, 32.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.00pt, 32.17pt), text(size: 9pt, fill: black)[i])
})]),
  alt: "A graph has 9 vertices. The vertices are labeled from a to i. The edges are f c, c d, c a, a b, b e, e h, b g, and g i.", caption: [Spanning Tree Formed Removing #emph[ad], #emph[af], and #emph[hi]],
)
]
]


    
    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Chains of Affection]


      Here is a strange question to ask in a math class: Have you ever dated your ex’s new partner’s ex? Research suggests that your answer is probably no. When researchers Peter S. Bearman, James Moody, and Katherine Stovel attempted to compare the structure of heterosexual romantic networks at a typical midwestern high school to simulated networks, they found something surprising. The actual social networks were more like spanning trees than other possible models because there were very few short cycles. In particular, there were almost no four-cycles.


      #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 45.23pt), (0.00pt, -45.23pt), stroke: 0.7pt + black)
  line((45.23pt, 0.00pt), (-45.23pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -45.23pt), (-45.23pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 45.23pt), (45.23pt, 0.00pt), stroke: 0.7pt + black)
  content((0.00pt, 10.85pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[time 1])
  content((0.00pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[time 1])
  content((-22.61pt, -22.61pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[time 2])
  content((22.61pt, 22.61pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[?])
  circle((0.00pt, 45.23pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.23pt), text(size: 9pt, fill: black)[Bob])
  circle((45.23pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((52.23pt, 0.00pt), anchor: "west", text(size: 9pt)[Alice])
  circle((0.00pt, -45.23pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -63.93pt), anchor: "north", text(size: 9pt)[Carol])
  circle((-45.23pt, -0.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-45.23pt, -0.00pt), text(size: 9pt, fill: black)[Ted])
  line((2.58pt, -45.51pt), (0.00pt, -41.23pt), (-2.58pt, -45.51pt), fill: black, stroke: none, close: true)
  line((-38.01pt, -2.58pt), (-33.73pt, -0.00pt), (-38.01pt, 2.58pt), fill: black, stroke: none, close: true)
  line((-41.95pt, -6.92pt), (-37.09pt, -8.13pt), (-38.30pt, -3.28pt), fill: black, stroke: none, close: true)
  line((47.25pt, 1.62pt), (42.40pt, 2.83pt), (43.61pt, -2.02pt), fill: black, stroke: none, close: true)
})]),
  alt: "A graph with four vertices. The vertices are Bob, Alice, Carol, and Ted. A double-headed arrow labeled time 1 is between Bob and Carol. A double-headed arrow labeled time 1 is between Alice and Tex. A double-headed arrow labeled time 2 is between Carol and Ted. A double-headed arrow labeled with a question mark is between Bob and Alice.", caption: [Chains of Affection],
)


      “…the prohibition against dating (from a female perspective) one’s old boyfriend’s current girlfriend’s old boyfriend – accounts for the structure of the romantic network at \[the highschool\].”


      In their article “Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks,” the researchers went on to explain the implications for the transmission of sexually transmitted diseases. In particular, social structures based on tree graphs are less dense and more likely to fragment. This information can impact social policies on disease prevention. (Peter S. Bearman, James Moody, and Katherine Stovel, “Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks,” #emph[American Journal of Sociology] Volume 110, Number 1, pp. 44-91, 2004)
]


  
  
    
=== Kruskal’s Algorithm


    In many applications of spanning trees, the graphs are weighted and we want to find the spanning tree of least possible weight. For example, the graph might represent a computer network, and the weights might represent the cost involved in connecting two devices. So, finding a spanning tree with the lowest possible total weight, or #strong[minimum spanning tree], means saving money! The method that we will use to find a minimum spanning tree of a weighted graph is called #strong[Kruskal’s algorithm]. The steps for Kruskal’s algorithm are:


    #strong[Step 1:] Choose any edge with the minimum weight of all edges.


    #strong[Step 2:] Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.


    #strong[Step 3:] Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.


    #strong[Step 4:] Repeat step 3 until all the vertices of the original graph are included and you have a spanning tree.


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Trees_in_Graph_Theory")[Use Kruskal's Algorithm to Find Minimum Spanning Trees in Graph Theory]
]


    #examplebox("Example 7")[Using Kruskal’s Algorithm][
A computer network will be set up with six devices. The vertices in the graph in  represent the devices, and the edges represent the cost of a connection. Find the network configuration that will cost the least. What is the total cost?


        #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((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), (-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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars.", caption: [Graph of Network Connection Costs],
)


      
      #solutionbox[
A minimum spanning tree will correspond to the network configuration of least cost. We will use Kruskal’s algorithm to find one. Since the graph has six vertices, the spanning tree will have six vertices and five edges.


        #strong[Step 1:] Choose an edge of least weight. We have sorted the weights into numerical order. The least is \$100. The only edge of this weight is edge #emph[AF] as shown.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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), (-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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edge, A F is in dashed lines. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100 is struck through.", caption: [Step 1 Select Edge #emph[AF]],
)


        #strong[Step 2:] Choose the edge of least weight of the remaining edges, which is #emph[BD] with \$120. Notice that the two selected edges do not need to be adjacent to each other as shown.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edges, A F, and B D are in dashed lines. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100 and 120 are struck through.", caption: [Step 2 Select Edge #emph[BD]],
)


        #strong[Step 3:] Select the lowest weight edge of the remaining edges, as long as it does not result in a cycle. We select #emph[DF] with \$150 since it does not form a cycle as shown.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edges, A F, B D, and D F are in dashed lines. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100, 120, and 150 are struck through.", caption: [Step 3 Select Edge #emph[DF]],
)


        #strong[Repeat Step 3:] Select the lowest weight edge of the remaining edges, which is #emph[BE] with \$160 and it does not form a cycle as shown. This gives us four edges so we only need to repeat step 3 once more to get the fifth edge.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edges, A F, B D, B E, and D F are in dashed lines. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100, 120, 150, and 160 are struck through.", caption: [Repeat Step 3 Select Edge #emph[DF]],
)


        #strong[Repeat Step 3:] The lowest weight of the remaining edges is \$170. Both #emph[BF] and #emph[CE] have a weight of \$170, but #emph[BF] would create cycle (#emph[b], #emph[d], #emph[f]) and there cannot be a cycle in a spanning tree as shown.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  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)
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edges, A F, B D, B E, and DF are in dashed lines. Edge, B F is in red. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100, 120, 150, and 160 are struck through. 170 is crossed out.", caption: [Repeat Step 3 Do Not Select Edge #emph[BF]],
)


        So, we will select #emph[CE], which will complete the spanning tree as shown.


        #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((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  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), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, -21.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), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  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])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. Edges, A F, B D, B E, C E, and D F are in dashed lines. Cost in dollars are as follows: 100, 120, 150, 160, 170, 170, 200, 210, 220, 250, 270, 300, 310, 330, and 350. 100, 120, 150, 160, and 170 are struck through. 170 is crossed out.", caption: [Repeat Step 3 Select Edge #emph[CE]],
)


        The minimum spanning tree is shown. This is the configuration of the network of least cost. The spanning tree has a total weight of #math.equation(block: false, alt: "$ 100 plus $ 120 plus $ 150 plus $ 160 plus $ 170 equals $ 700")[$\$ 100 + \$ 120 + \$ 150 + \$ 160 + \$ 170 = \$ 700$], which is the total cost of this network configuration.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((-18.19pt, 31.50pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((0.00pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((18.19pt, -10.50pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((8.73pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((-18.19pt, -10.50pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  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])
})]),
  alt: "A graph has six vertices labeled A to F. The edges are as follows. A F, curved edge, 100 dollars. B E, 160 dollars. B D, 120 dollars. C E, 170 dollars. D F, 150 dollars.", caption: [Final Minimum Spanning Tree],
)
]
]


    
  
  
  
  
    
=== Key Terms


    - acyclic
- tree
- forest
- path graph or linear graph
- star tree
- root
- starlike tree
- caterpillar tree
- lobster tree
- spanning tree
- minimum spanning tree


  
  
    
=== Key Concepts


    - A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
- A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
- The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
- The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.


  
  
    
=== Videos


    - #link("https://openstax.org/r/Hunting_Numberphile")[The Problem in #emph[Good Will Hunting] by Numberphile]
- #link("https://openstax.org/r/Spanning_Trees_in_Graph_Theory")[Spanning Trees in Graph Theory]
- #link("https://openstax.org/r/Trees_in_Graph_Theory")[Use Kruskal's Algorithm to Find Minimum Spanning Trees in Graph Theory]


  
  
    
=== Formulas


    - The number of edges in a tree graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "n minus 1")[$n − 1$]. A connected graph with n vertices and #math.equation(block: false, alt: "n minus 1")[$n − 1$] edges is a tree graph.


  
  
    
=== Projects


    #strong[Everyone Gets a Turn! – Graph Colorings]


    Let’s put your knowledge of graph colorings to work! Your task is to plan a field day following these steps.


    + Select between seven and ten activities for your field day. You can look online for ideas.
+ Create a survey asking for the participants to select the three to five events in which they would most like to participate. Survey between seven and ten people.
+ Use the results of your survey to create a graph in which each vertex represents one of the events. A pair of vertices will be adjacent if there is at least one participant who would like to participate in both events.
+ Find a minimum coloring for the graph. Explain how you found it and how you know the chromatic number of the graph.
+ Use your solution to part d to determine the minimum number of timeslots you must use to ensure that everyone has the opportunity to participate in their top three events.
+ Find the complement of the graph you created. Explain what the edges in this graph represent.


    #strong[A Beautiful Day in the Neighborhood – Euler Circuits]


    Let’s apply what you have learned to the community in which you live. Using resources such as your county’s property appraiser’s website, create a detailed graph of your neighborhood in which vertices represent turns and intersections. Represent a large enough part of your community to include no fewer than 10 intersections or turns. Then use your graph to answer the following questions.


    + Label the edges of your graph.
+ Determine if your graph is Eulerian. Explain how you know. If it is not, eulerize it.
+ Find an Euler circuit for your graph. Give the sequence of vertices that you found.
+ What does the Euler circuit you found in part c represent for your community?
+ Describe an application for which this Euler circuit might be used.


    #strong[Dream Vacation – Hamilton Cycles and Paths]


    Where in the world would you like to travel most: the Eiffel Tower in Paris, a Broadway musical in New York city, a bike tour of Amsterdam, the Tenerife whale and dolphin cruises in the Canary Islands, the Giza Pyramid in Cairo, or maybe the Jokhang Temple in Tibet? Let's plan your dream vacation!


    + Which four destinations are at the top of your bucket list?
+ Draw a complete weighted graph with five vertices representing the four destinations and your home city, and the weights representing the cost of travel between cities.
+ Use a website (such as #link("https://openstax.org/r/travelocity")[Travelocity]) to find the best airfare between each pair of cities. List the airlines and flight numbers along with the prices. Include cost for ground transportation from the nearest airport if there is no airport at the destination you want to visit.
+ Use the nearest neighbor algorithm to find a Hamilton cycle of low weight beginning and ending in your hometown. What is the weight of this circuit and what does it represent?
+ Use the brute force method to find a Hamilton cycle of lowest weight beginning and ending in your hometown. What is the weight of this circuit? Is it the same or different from the weight of the Hamilton cycle you found in Exercise 4?
+ Suppose that instead of returning home, you planned to move to your favorite location on the list, but you wanted to stop at the other three destinations once along the way. Where would you move? List all Hamilton paths between your hometown and your favorite location.
+ Find the weights of all the Hamilton paths you found in Exercise 6.