#set document(title: "12.6 Euler Trails", 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.6#h(0.6em)Euler Trails


  #figure(figph[A map of the United States shows the Pony Express mail route. The route began in St. Joseph, Missouri and traveled through Fort Kearney, Nebraska; Julesburg, Colorado; Fort Laramie, Wyoming; Fort Bridger, Wyoming; Salt Lake City, Utah; Fort Ruby, Nevada; Carson City, Nevada; and San Francisco, California.], alt: "A map of the United States shows the Pony Express mail route. The route began in St. Joseph, Missouri and traveled through Fort Kearney, Nebraska; Julesburg, Colorado; Fort Laramie, Wyoming; Fort Bridger, Wyoming; Salt Lake City, Utah; Fort Ruby, Nevada; Carson City, Nevada; and San Francisco, California.", caption: [The Pony Express mail route spanned from California to Missouri.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Describe and identify Euler trails.
+ Solve applications using Euler trails theorem.
+ Identify bridges in a graph.
+ Apply Fleury’s algorithm.
+ Evaluate Euler trails in real-world applications.


  
  We used Euler circuits to help us solve problems in which we needed a route that started and ended at the same place. In many applications, it is not necessary for the route to end where it began. In other words, we may not be looking at circuits, but trails, like the old Pony Express trail that led from Sacramento, California in the west to St. Joseph, Missouri in the east, never backtracking.


  
    
=== Euler Trails


    If we need a trail that visits every edge in a graph, this would be called an #strong[Euler trail]. Since trails are walks that do not repeat edges, an Euler trail visits every edge exactly once.


    #examplebox("Example 1")[Recognizing Euler Trails][
Use  to determine if each series of vertices represents a trail, an Euler trail, both, or neither. Explain your reasoning.


        #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 H])
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (18.22pt, -37.84pt), 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)
  line((18.22pt, -37.84pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((40.95pt, -9.35pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((-32.84pt, 26.19pt), (-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])
})]),
  alt: "Graph H has 7 vertices labeled a to g. The edges connect a b, a d, b e, e d, d c, c f, f g, d g, and g e.", caption: [Graph #emph[H]],
)


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


      
      #solutionbox[
+ It is a trail only. It is a trail because it is a walk that doesn’t cover any edges twice, but it is not an Euler trail because it didn’t cover edges #emph[ad] or #emph[dg].
+ It is neither. It is not a trail because it visits #emph[ab] and #emph[be] twice. Since it is not a trail, it cannot be an Euler trail.
+ It is both. It is a trail because it is a walk that doesn’t cover any edges twice, and it is an Euler trail because it visits all the edges.
]
]


    
  
  
    
=== The Five Rooms Puzzle


    Just as Euler determined that only graphs with vertices of even degree have Euler circuits, he also realized that the only vertices of odd degree in a graph with an Euler trail are the starting and ending vertices. For example, in , Graph #emph[H] has exactly two vertices of odd degree, vertex #emph[g] and vertex #emph[e]. Notice the Euler trail we saw in Excercise 3 of Example 1 began at vertex #emph[g] and ended at vertex #emph[e].


    This is consistent with what we learned about vertices off odd degree when we were studying Euler circuits. We saw that a vertex of odd degree couldn't exist in an Euler circuit as depicted in . If it was a starting vertex, at some point we would leave the vertex and not be able to return without repeating an edge. If it was not a starting vertex, at some point we would return and not be able to leave without repeating an edge. Since the starting and ending vertices in an Euler trail are not the same, the start is a vertex we want to leave without returning, and the end is a vertex we want to return to and never leave. Those two vertices must have odd degree, but the others cannot.


    #figure(figph[Two illustrations. The first illustration shows a vertex, 3. Two arrows point to it and an arrow points away from it. The second illustration shows a vertex, 3. Two arrows point away from it and an arrow points to it.], alt: "Two illustrations. The first illustration shows a vertex, 3. Two arrows point to it and an arrow points away from it. The second illustration shows a vertex, 3. Two arrows point away from it and an arrow points to it.", caption: [A Vertex of Degree 3])


    Let’s use the Euler trail theorem to solve a puzzle so you can amaze your friends! This puzzle is called the “Five Rooms Puzzle.” Suppose that you were in a house with five rooms and the exterior. There is a doorway in every shared wall between any two rooms and between any room and the exterior as shown. Could you find a route through the house that passes through each doorway exactly once?


    #figure(figph[An illustration shows five rooms in a rectangle labeled f. The rooms are labeled a to e.], alt: "An illustration shows five rooms in a rectangle labeled f. The rooms are labeled a to e.", caption: [Five Rooms Puzzle])


    Let’s represent the puzzle with a graph in which vertices are rooms (or the exterior) and an edge indicates a door between two rooms 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), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  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)
  bezier((36.37pt, -21.00pt), (-36.37pt, 21.00pt), (2.10pt, 3.64pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  bezier((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), (-32.17pt, -0.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, 42.00pt), (-36.37pt, 21.00pt), (-20.29pt, 35.14pt), stroke: 0.7pt + black)
  bezier((0.00pt, 42.00pt), (-36.37pt, 21.00pt), (-16.09pt, 27.86pt), stroke: 0.7pt + black)
  bezier((36.37pt, 21.00pt), (-36.37pt, 21.00pt), (0.00pt, 25.20pt), stroke: 0.7pt + black)
  bezier((36.37pt, 21.00pt), (-36.37pt, 21.00pt), (-0.00pt, 16.80pt), stroke: 0.7pt + black)
  bezier((36.37pt, -21.00pt), (-36.37pt, 21.00pt), (-2.10pt, -3.64pt), stroke: 0.7pt + black)
  bezier((-36.37pt, 21.00pt), (-36.37pt, -21.00pt), (-32.17pt, -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((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: "An illustration shows five rooms in a rectangle labeled f. An arrow from the illustration points to a graph with six vertices. In the illustration, the rooms are labeled a to e. The vertices are a to f. Edges interconnect all the vertices. In the graph, the vertices are labeled a to f. edges connect a b, a d, b d, b e, a c, c d, d e, c d, c f, d f, d e, and e f. Double curved edges connect a to f and b to f. Curved edges connect c to f and f to e.", caption: [Graph of Five Rooms Puzzle],
)


    To pass through each doorway exactly once means that we cross every edge in the graph exactly once. Since we have not been asked to start and end at the same position, but to visit each edge exactly once, we are looking for an Euler trail. Let’s check the degrees of the vertices.


    #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), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  bezier((36.37pt, -21.00pt), (0.00pt, -42.00pt), (16.09pt, -27.86pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-36.37pt, -21.00pt), (-16.09pt, -27.86pt), stroke: 0.7pt + black)
  bezier((36.37pt, -21.00pt), (0.00pt, -42.00pt), (20.29pt, -35.14pt), stroke: 0.7pt + black)
  bezier((36.37pt, -21.00pt), (-36.37pt, 21.00pt), (2.10pt, 3.64pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-36.37pt, -21.00pt), (-20.29pt, -35.14pt), stroke: 0.7pt + black)
  bezier((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), (-32.17pt, -0.00pt), stroke: 0.7pt + black)
  bezier((0.00pt, 42.00pt), (-36.37pt, 21.00pt), (-20.29pt, 35.14pt), stroke: 0.7pt + black)
  bezier((0.00pt, 42.00pt), (-36.37pt, 21.00pt), (-16.09pt, 27.86pt), stroke: 0.7pt + black)
  bezier((36.37pt, 21.00pt), (-36.37pt, 21.00pt), (0.00pt, 25.20pt), stroke: 0.7pt + black)
  bezier((36.37pt, 21.00pt), (-36.37pt, 21.00pt), (-0.00pt, 16.80pt), stroke: 0.7pt + black)
  bezier((36.37pt, -21.00pt), (-36.37pt, 21.00pt), (-2.10pt, -3.64pt), stroke: 0.7pt + black)
  bezier((-36.37pt, 21.00pt), (-36.37pt, -21.00pt), (-32.17pt, -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((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 a to f and their degrees are 5, 5, 4, 5, 4, and 9. Edges connect a b, a d, b d, b e, a c, c d, d e, c d, c f, d f, d e, and e f. Double curved edges connect a to f and b to f. Curved edges connect c to f and f to e.", caption: [Degrees of Vertices in Five Rooms Puzzle],
)


    Since there are more than two vertices of odd degree as shown in , the graph of the five rooms puzzle contains no Euler path. Now you can amaze and astonish your friends!


  
  
    
=== Bridges and Local Bridges


    Now that we know which graphs have Euler trails, let’s work on a method to find them. The method we will use involves identifying #strong[bridges] in our graphs. A bridge is an edge which, if removed, increases the number of components in a graph. Bridges are often referred to as cut-edges. In , there are several examples of bridges. Notice that an edge that is not part of a cycle is always a bridge, and an edge that is part of a cycle is never a bridge.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 49.83pt), (26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (0.00pt, 49.83pt), stroke: 0.7pt + black)
  line((-14.04pt, -47.82pt), (-26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((-26.94pt, 41.92pt), (-45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((-45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((37.66pt, -32.63pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((14.04pt, -47.82pt), (-37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((-37.66pt, -32.63pt), (-49.33pt, -7.09pt), stroke: 0.7pt + black)
  line((-49.33pt, -7.09pt), (37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((49.33pt, -7.09pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  circle((0.00pt, 49.83pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 49.83pt), text(size: 9pt, fill: black)[a])
  circle((26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.94pt, 41.92pt), text(size: 9pt, fill: black)[b])
  circle((45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((45.33pt, 20.70pt), text(size: 9pt, fill: black)[c])
  circle((49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -7.09pt), text(size: 9pt, fill: black)[d])
  circle((37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.66pt, -32.63pt), text(size: 9pt, fill: black)[e])
  circle((14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -47.82pt), text(size: 9pt, fill: black)[f])
  circle((-14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -47.82pt), text(size: 9pt, fill: black)[g])
  circle((-37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.66pt, -32.63pt), text(size: 9pt, fill: black)[h])
  circle((-49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -7.09pt), text(size: 9pt, fill: black)[i])
  circle((-45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-45.33pt, 20.70pt), text(size: 9pt, fill: black)[j])
  circle((-26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.94pt, 41.92pt), text(size: 9pt, fill: black)[k])
})]),
  alt: "A graph has two triangles and one square. The first triangle has vertices, a, b, and c. The second triangle has vertices, g, k, and j. The square has the vertices, e, f, h, and i. An edge connects e and i. The bridges connect b f, c g, and d g.", caption: [Graph with Bridges],
)


    Edges #emph[bf], #emph[cg], and #emph[dg] are “bridges”


    The graph in  is connected, which means it has exactly one component. Each time we remove one of the bridges from the graph the number of components increases by one as shown. If we remove all three, the resulting graph in  has four components.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 49.83pt), (26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (0.00pt, 49.83pt), stroke: 0.7pt + black)
  line((-14.04pt, -47.82pt), (-26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((-26.94pt, 41.92pt), (-45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((-45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((37.66pt, -32.63pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((14.04pt, -47.82pt), (-37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((-37.66pt, -32.63pt), (-49.33pt, -7.09pt), stroke: 0.7pt + black)
  line((-49.33pt, -7.09pt), (37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((49.33pt, -7.09pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  circle((0.00pt, 49.83pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 49.83pt), text(size: 9pt, fill: black)[a])
  circle((26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.94pt, 41.92pt), text(size: 9pt, fill: black)[b])
  circle((45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((45.33pt, 20.70pt), text(size: 9pt, fill: black)[c])
  circle((49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -7.09pt), text(size: 9pt, fill: black)[d])
  circle((37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.66pt, -32.63pt), text(size: 9pt, fill: black)[e])
  circle((14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -47.82pt), text(size: 9pt, fill: black)[f])
  circle((-14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -47.82pt), text(size: 9pt, fill: black)[g])
  circle((-37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.66pt, -32.63pt), text(size: 9pt, fill: black)[h])
  circle((-49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -7.09pt), text(size: 9pt, fill: black)[i])
  circle((-45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-45.33pt, 20.70pt), text(size: 9pt, fill: black)[j])
  circle((-26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.94pt, 41.92pt), text(size: 9pt, fill: black)[k])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 49.83pt), (26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (0.00pt, 49.83pt), stroke: 0.7pt + black)
  line((-14.04pt, -47.82pt), (-26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((-26.94pt, 41.92pt), (-45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((-45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((37.66pt, -32.63pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((14.04pt, -47.82pt), (-37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((-37.66pt, -32.63pt), (-49.33pt, -7.09pt), stroke: 0.7pt + black)
  line((-49.33pt, -7.09pt), (37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((49.33pt, -7.09pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  circle((0.00pt, 49.83pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 49.83pt), text(size: 9pt, fill: black)[a])
  circle((26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.94pt, 41.92pt), text(size: 9pt, fill: black)[b])
  circle((45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((45.33pt, 20.70pt), text(size: 9pt, fill: black)[c])
  circle((49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -7.09pt), text(size: 9pt, fill: black)[d])
  circle((37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.66pt, -32.63pt), text(size: 9pt, fill: black)[e])
  circle((14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -47.82pt), text(size: 9pt, fill: black)[f])
  circle((-14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -47.82pt), text(size: 9pt, fill: black)[g])
  circle((-37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.66pt, -32.63pt), text(size: 9pt, fill: black)[h])
  circle((-49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -7.09pt), text(size: 9pt, fill: black)[i])
  circle((-45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-45.33pt, 20.70pt), text(size: 9pt, fill: black)[j])
  circle((-26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.94pt, 41.92pt), text(size: 9pt, fill: black)[k])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 49.83pt), (26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (0.00pt, 49.83pt), stroke: 0.7pt + black)
  line((-14.04pt, -47.82pt), (-26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((-26.94pt, 41.92pt), (-45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((-45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((37.66pt, -32.63pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((14.04pt, -47.82pt), (-37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((-37.66pt, -32.63pt), (-49.33pt, -7.09pt), stroke: 0.7pt + black)
  line((-49.33pt, -7.09pt), (37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((49.33pt, -7.09pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  circle((0.00pt, 49.83pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 49.83pt), text(size: 9pt, fill: black)[a])
  circle((26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.94pt, 41.92pt), text(size: 9pt, fill: black)[b])
  circle((45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((45.33pt, 20.70pt), text(size: 9pt, fill: black)[c])
  circle((49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -7.09pt), text(size: 9pt, fill: black)[d])
  circle((37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.66pt, -32.63pt), text(size: 9pt, fill: black)[e])
  circle((14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -47.82pt), text(size: 9pt, fill: black)[f])
  circle((-14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -47.82pt), text(size: 9pt, fill: black)[g])
  circle((-37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.66pt, -32.63pt), text(size: 9pt, fill: black)[h])
  circle((-49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -7.09pt), text(size: 9pt, fill: black)[i])
  circle((-45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-45.33pt, 20.70pt), text(size: 9pt, fill: black)[j])
  circle((-26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.94pt, 41.92pt), text(size: 9pt, fill: black)[k])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 49.83pt), (26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((26.94pt, 41.92pt), (45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((45.33pt, 20.70pt), (0.00pt, 49.83pt), stroke: 0.7pt + black)
  line((-14.04pt, -47.82pt), (-26.94pt, 41.92pt), stroke: 0.7pt + black)
  line((-26.94pt, 41.92pt), (-45.33pt, 20.70pt), stroke: 0.7pt + black)
  line((-45.33pt, 20.70pt), (-14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((37.66pt, -32.63pt), (14.04pt, -47.82pt), stroke: 0.7pt + black)
  line((14.04pt, -47.82pt), (-37.66pt, -32.63pt), stroke: 0.7pt + black)
  line((-37.66pt, -32.63pt), (-49.33pt, -7.09pt), stroke: 0.7pt + black)
  line((-49.33pt, -7.09pt), (37.66pt, -32.63pt), stroke: 0.7pt + black)
  circle((0.00pt, 49.83pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 49.83pt), text(size: 9pt, fill: black)[a])
  circle((26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.94pt, 41.92pt), text(size: 9pt, fill: black)[b])
  circle((45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((45.33pt, 20.70pt), text(size: 9pt, fill: black)[c])
  circle((49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.33pt, -7.09pt), text(size: 9pt, fill: black)[d])
  circle((37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.66pt, -32.63pt), text(size: 9pt, fill: black)[e])
  circle((14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -47.82pt), text(size: 9pt, fill: black)[f])
  circle((-14.04pt, -47.82pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -47.82pt), text(size: 9pt, fill: black)[g])
  circle((-37.66pt, -32.63pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.66pt, -32.63pt), text(size: 9pt, fill: black)[h])
  circle((-49.33pt, -7.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.33pt, -7.09pt), text(size: 9pt, fill: black)[i])
  circle((-45.33pt, 20.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-45.33pt, 20.70pt), text(size: 9pt, fill: black)[j])
  circle((-26.94pt, 41.92pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.94pt, 41.92pt), text(size: 9pt, fill: black)[k])
})]
)]),
  alt: "Four graphs. The first graph has two triangles and a square. The first triangle has vertices, a, b, and c. The second triangle has vertices, g, k, and j. The square has the vertices, e, f, h, and i. An edge connects e and i. The bridges connect b f, c g, and d g. The second graph is the same. The square is separated. The third graph shows the square and the triangles separated. The second triangle is connected to the vertex, d. In the fourth graph, the triangles, square, and the d vertex are separated.", caption: [Removing a Bridge Increases Number of Components],
)


    In sociology, bridges are a key part of social network analysis. Sociologists study two kinds of bridges: local bridges and regular bridges. Regular bridges are defined the same in sociology as in graph theory, but they are unusual when studying a large social network because it is very unlikely a group of individuals in a large social network has only one link to the rest of the network. On the other hand, a #strong[local bridge] occurs much more frequently. A local bridge is a friendship between two individuals who have no other friends in common. If they lose touch, there is no single individual who can pass information between them. In graph theory, a #strong[local bridge] is an edge between two vertices, which, when removed, increases the length of the shortest path between its vertices to more than two edges. In , a local bridge between vertices #emph[b] and #emph[e] has been removed. As a result, the shortest path between #emph[b] and #emph[e] is #emph[b] → #emph[i] → #emph[j] → #emph[k] → #emph[e], which is four edges. On the other hand, if edge #emph[ab] were removed, then there are still paths between #emph[a] and #emph[b] that cover only two edges, like #emph[a] → #emph[i] → #emph[b].


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (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), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (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), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (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), (-26.71pt, -36.76pt), 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)
  line((0.00pt, 45.43pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (26.71pt, -36.76pt), 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((0.00pt, -45.43pt), (-43.21pt, -14.04pt), 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)[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)[a])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), 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)[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)[j])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[k])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (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), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (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), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (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), (-26.71pt, -36.76pt), 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)
  line((0.00pt, 45.43pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), 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((0.00pt, -45.43pt), (-43.21pt, -14.04pt), 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)[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)[a])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), 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)[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)[j])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[k])
})]
)]),
  alt: "Two graphs. The first graph shows a triangle, i a b resting on a square, a b d e, and another triangle, k e f resting on a square, e f g h. The squares have diagonal lines. Edges connect i j and j k. A bridge connects b e. The second graph shows a triangle, i a b resting on a square, a b d e, and another triangle, k e f resting on a square, e f g h. The squares have diagonal lines. Bridges connect i j and j k.", caption: [Removing a Local Bridge],
)


    The significance of a local bridge in sociology is that it is the shortest communication route between two groups of people. If the local bridge is removed, the flow of information from one group to another becomes more difficult. Let’s say that vertex #emph[b] is Brielle and vertex #emph[e] is Ella. Now, Brielle is less likely to hear about things like job opportunities that Ella may know about. This is likely to impact Brielle as well as the friends of Brielle.


    #examplebox("Example 2")[Identifying Bridges and Local Bridges][
Use the graph of a social network in  to answer each question.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 103.11pt), (27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((27.82pt, 99.29pt), (53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((97.16pt, -34.53pt), (84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((0.00pt, 103.11pt), (75.36pt, 70.38pt), stroke: 0.7pt + black)
  line((27.82pt, 99.29pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((53.57pt, 88.10pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((97.16pt, -34.53pt), (102.87pt, -7.04pt), stroke: 0.7pt + black)
  line((75.36pt, 70.38pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((91.55pt, 47.44pt), (100.95pt, 20.98pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (102.87pt, -7.04pt), stroke: 0.7pt + black)
  line((75.36pt, 70.38pt), (-14.04pt, -102.15pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (65.07pt, -79.98pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((102.87pt, -7.04pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((65.07pt, -79.98pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((41.08pt, -94.57pt), (-91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((65.07pt, -79.98pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (14.04pt, -102.15pt), stroke: 0.7pt + black)
  line((14.04pt, -102.15pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (-65.07pt, -79.98pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((14.04pt, -102.15pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-41.08pt, -94.57pt), (-97.16pt, -34.53pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-75.36pt, 70.38pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((-65.07pt, -79.98pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-97.16pt, -34.53pt), stroke: 0.7pt + black)
  line((-75.36pt, 70.38pt), (-53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((-53.57pt, 88.10pt), (-27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((-65.07pt, -79.98pt), (-102.87pt, -7.04pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-100.95pt, 20.98pt), stroke: 0.7pt + black)
  line((-102.87pt, -7.04pt), (-100.95pt, 20.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 103.11pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 103.11pt), text(size: 9pt, fill: black)[a])
  circle((27.82pt, 99.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.82pt, 99.29pt), text(size: 9pt, fill: black)[b])
  circle((53.57pt, 88.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((53.57pt, 88.10pt), text(size: 9pt, fill: black)[c])
  circle((75.36pt, 70.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((75.36pt, 70.38pt), text(size: 9pt, fill: black)[d])
  circle((91.55pt, 47.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((91.55pt, 47.44pt), text(size: 9pt, fill: black)[e])
  circle((100.95pt, 20.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((100.95pt, 20.98pt), text(size: 9pt, fill: black)[f])
  circle((102.87pt, -7.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((102.87pt, -7.04pt), text(size: 9pt, fill: black)[g])
  circle((97.16pt, -34.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((97.16pt, -34.53pt), text(size: 9pt, fill: black)[h])
  circle((84.24pt, -59.46pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.24pt, -59.46pt), text(size: 9pt, fill: black)[i])
  circle((65.07pt, -79.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((65.07pt, -79.98pt), text(size: 9pt, fill: black)[j])
  circle((41.08pt, -94.57pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.08pt, -94.57pt), text(size: 9pt, fill: black)[k])
  circle((14.04pt, -102.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -102.15pt), text(size: 9pt, fill: black)[m])
  circle((-14.04pt, -102.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -102.15pt), text(size: 9pt, fill: black)[n])
  circle((-41.08pt, -94.57pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.08pt, -94.57pt), text(size: 9pt, fill: black)[o])
  circle((-65.07pt, -79.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-65.07pt, -79.98pt), text(size: 9pt, fill: black)[p])
  circle((-84.24pt, -59.46pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-84.24pt, -59.46pt), text(size: 9pt, fill: black)[q])
  circle((-97.16pt, -34.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-97.16pt, -34.53pt), text(size: 9pt, fill: black)[r])
  circle((-102.87pt, -7.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-102.87pt, -7.04pt), text(size: 9pt, fill: black)[s])
  circle((-100.95pt, 20.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-100.95pt, 20.98pt), text(size: 9pt, fill: black)[t])
  circle((-91.55pt, 47.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-91.55pt, 47.44pt), text(size: 9pt, fill: black)[u])
  circle((-75.36pt, 70.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-75.36pt, 70.38pt), text(size: 9pt, fill: black)[v])
  circle((-53.57pt, 88.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-53.57pt, 88.10pt), text(size: 9pt, fill: black)[w])
  circle((-27.82pt, 99.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.82pt, 99.29pt), text(size: 9pt, fill: black)[x])
})]),
  alt: "A graph with 23 vertices. The edges are as follows: a b, b c, h i, a d, b e, c e, h g, d e, e f, f g, d n, f j, f k, g k, j k, k u, j o, n m, m o, n p, n q, m q, q o, o r, u v, u w, u x, p q, q r, v w, w x, p s, q t, and s t.", caption: [Graph of a Social Network],
)


        + Identify any bridges.
+ If all bridges were removed, how many components would there be in the resulting graph?
+ Identify one local bridge.
+ For the local bridge you identified in part 3, identify the shortest path between the vertices of the local bridge if the local bridge were removed.


      
      #solutionbox[
+ The edges #emph[ku, gh], and #emph[hi] are bridges.
+ If the bridges were all removed, there would be four components in the resulting graph, {#emph[i]}, {#emph[h]}, {#emph[u], #emph[v], #emph[w], #emph[x]}, and {#emph[a], #emph[b], #emph[c], #emph[d], #emph[e], #emph[f], #emph[g], #emph[j], #emph[k], #emph[m], #emph[n], #emph[o], #emph[p], #emph[q], #emph[r], #emph[s], #emph[t]} as shown.
  #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 103.11pt), (27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((27.82pt, 99.29pt), (53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((0.00pt, 103.11pt), (75.36pt, 70.38pt), stroke: 0.7pt + black)
  line((27.82pt, 99.29pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((53.57pt, 88.10pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((75.36pt, 70.38pt), (91.55pt, 47.44pt), stroke: 0.7pt + black)
  line((91.55pt, 47.44pt), (100.95pt, 20.98pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (102.87pt, -7.04pt), stroke: 0.7pt + black)
  line((75.36pt, 70.38pt), (-14.04pt, -102.15pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (65.07pt, -79.98pt), stroke: 0.7pt + black)
  line((100.95pt, 20.98pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((102.87pt, -7.04pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((65.07pt, -79.98pt), (41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((65.07pt, -79.98pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (14.04pt, -102.15pt), stroke: 0.7pt + black)
  line((14.04pt, -102.15pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (-65.07pt, -79.98pt), stroke: 0.7pt + black)
  line((-14.04pt, -102.15pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((14.04pt, -102.15pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-41.08pt, -94.57pt), stroke: 0.7pt + black)
  line((-41.08pt, -94.57pt), (-97.16pt, -34.53pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-75.36pt, 70.38pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((-91.55pt, 47.44pt), (-27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((-65.07pt, -79.98pt), (-84.24pt, -59.46pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-97.16pt, -34.53pt), stroke: 0.7pt + black)
  line((-75.36pt, 70.38pt), (-53.57pt, 88.10pt), stroke: 0.7pt + black)
  line((-53.57pt, 88.10pt), (-27.82pt, 99.29pt), stroke: 0.7pt + black)
  line((-65.07pt, -79.98pt), (-102.87pt, -7.04pt), stroke: 0.7pt + black)
  line((-84.24pt, -59.46pt), (-100.95pt, 20.98pt), stroke: 0.7pt + black)
  line((-102.87pt, -7.04pt), (-100.95pt, 20.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 103.11pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 103.11pt), text(size: 9pt, fill: black)[a])
  circle((27.82pt, 99.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.82pt, 99.29pt), text(size: 9pt, fill: black)[b])
  circle((53.57pt, 88.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((53.57pt, 88.10pt), text(size: 9pt, fill: black)[c])
  circle((75.36pt, 70.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((75.36pt, 70.38pt), text(size: 9pt, fill: black)[d])
  circle((91.55pt, 47.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((91.55pt, 47.44pt), text(size: 9pt, fill: black)[e])
  circle((100.95pt, 20.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((100.95pt, 20.98pt), text(size: 9pt, fill: black)[f])
  circle((102.87pt, -7.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((102.87pt, -7.04pt), text(size: 9pt, fill: black)[g])
  circle((97.16pt, -34.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((97.16pt, -34.53pt), text(size: 9pt, fill: black)[h])
  circle((84.24pt, -59.46pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((84.24pt, -59.46pt), text(size: 9pt, fill: black)[i])
  circle((65.07pt, -79.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((65.07pt, -79.98pt), text(size: 9pt, fill: black)[j])
  circle((41.08pt, -94.57pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((41.08pt, -94.57pt), text(size: 9pt, fill: black)[k])
  circle((14.04pt, -102.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((14.04pt, -102.15pt), text(size: 9pt, fill: black)[m])
  circle((-14.04pt, -102.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-14.04pt, -102.15pt), text(size: 9pt, fill: black)[n])
  circle((-41.08pt, -94.57pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-41.08pt, -94.57pt), text(size: 9pt, fill: black)[o])
  circle((-65.07pt, -79.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-65.07pt, -79.98pt), text(size: 9pt, fill: black)[p])
  circle((-84.24pt, -59.46pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-84.24pt, -59.46pt), text(size: 9pt, fill: black)[q])
  circle((-97.16pt, -34.53pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-97.16pt, -34.53pt), text(size: 9pt, fill: black)[r])
  circle((-102.87pt, -7.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-102.87pt, -7.04pt), text(size: 9pt, fill: black)[s])
  circle((-100.95pt, 20.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-100.95pt, 20.98pt), text(size: 9pt, fill: black)[t])
  circle((-91.55pt, 47.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-91.55pt, 47.44pt), text(size: 9pt, fill: black)[u])
  circle((-75.36pt, 70.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-75.36pt, 70.38pt), text(size: 9pt, fill: black)[v])
  circle((-53.57pt, 88.10pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-53.57pt, 88.10pt), text(size: 9pt, fill: black)[w])
  circle((-27.82pt, 99.29pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.82pt, 99.29pt), text(size: 9pt, fill: black)[x])
})]),
  alt: "A graph with 23 vertices. The edges are as follows: a b, b c, a d, b e, c e, d e, e f, f g, d n, f j, f k, g k, j k, j o, n m, m o, n p, n q, m q, q o, o r, u v, u w, u x, p q, q r, v w, w x, p s, q t, and s t. The vertices h and i are separated. The graph is divided into two blocks.", caption: [Graph of Social Network without Bridges],
)
+ Three local bridges are #emph[dn, ef], and #emph[qt], among others.
+ If #emph[dn] were removed, the shortest path between #emph[d] and #emph[n] would be #emph[d] → #emph[e] → #emph[f] → #emph[j] → #emph[o] → #emph[m] → #emph[n].
]
]


    
    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/bridges_local_bridges")[Bridges and Local Bridges in Graph Theory]
]


  
  
    
=== Finding an Euler Trail with Fleury’s Algorithm


    Now that we are familiar with bridges, we can use a technique called #strong[Fleury’s algorithm], which is a series of steps, or algorithm, used to find an Euler trail in any graph that has exactly two vertices of odd degree.


    Here are the steps involved in applying Fleury’s algorithm.


    #strong[Step 1:] Begin at either of the two vertices of odd degree.


    #strong[Step 2:] Remove an edge between the vertex and any adjacent vertex that is NOT a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all edges are removed.


    #strong[Step 3:] Write out the Euler trail using the sequence of vertices and edges that you found. For example, if you removed #emph[ab, bc, cd, de], and #emph[ef], in that order, then the Euler trail is #emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[e] → #emph[f].


    shows the steps to find an Euler trail in a graph using Fleury’s algorithm.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 1.4pt))
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 1.4pt))
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 1.4pt))
  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), (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)[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)[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((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[w])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[x])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[y])
  line((37.04pt, 23.59pt), (32.04pt, 23.50pt), (34.46pt, 19.13pt), fill: black, stroke: none, close: true)
  line((38.25pt, -19.09pt), (33.87pt, -16.67pt), (33.78pt, -21.67pt), fill: black, stroke: none, close: true)
  line((2.58pt, -41.28pt), (0.00pt, -37.00pt), (-2.58pt, -41.28pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 63.44pt), (54.94pt, 31.72pt), stroke: 0.7pt + black)
  line((54.94pt, 31.72pt), (0.00pt, -63.44pt), stroke: 0.7pt + black)
  line((0.00pt, -63.44pt), (-54.94pt, 31.72pt), stroke: 0.7pt + black)
  line((-54.94pt, 31.72pt), (-54.94pt, -31.72pt), stroke: 0.7pt + black)
  bezier((-54.94pt, -31.72pt), (54.94pt, -31.72pt), (0.00pt, -35.92pt), stroke: 0.7pt + black)
  line((54.94pt, -31.72pt), (0.00pt, -63.44pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  bezier((54.94pt, -31.72pt), (-54.94pt, -31.72pt), (0.00pt, -35.92pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((54.94pt, -31.72pt), (0.00pt, 63.44pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  content((20.88pt, 27.28pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove tv])
  circle((0.00pt, 63.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 63.44pt), text(size: 9pt, fill: black)[t])
  circle((54.94pt, 31.72pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.94pt, 31.72pt), text(size: 9pt, fill: black)[u])
  circle((54.94pt, -31.72pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.94pt, -31.72pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -63.44pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -63.44pt), text(size: 9pt, fill: black)[w])
  circle((-54.94pt, -31.72pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.94pt, -31.72pt), text(size: 9pt, fill: black)[x])
  circle((-54.94pt, 31.72pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.94pt, 31.72pt), text(size: 9pt, fill: black)[y])
  line((1.91pt, -65.31pt), (4.33pt, -60.94pt), (-0.67pt, -60.85pt), fill: black, stroke: none, close: true)
  line((-59.41pt, -33.96pt), (-54.94pt, -31.72pt), (-59.02pt, -28.82pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 77.00pt), (66.68pt, 38.50pt), stroke: 0.7pt + black)
  bezier((66.68pt, 38.50pt), (0.00pt, -77.00pt), (29.70pt, -17.15pt), stroke: 0.7pt + black)
  line((0.00pt, -77.00pt), (-66.68pt, 38.50pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((-66.68pt, 38.50pt), (-66.68pt, -38.50pt), stroke: 0.7pt + black)
  line((-66.68pt, -38.50pt), (66.68pt, -38.50pt), stroke: 0.7pt + black)
  line((66.68pt, -38.50pt), (0.00pt, -77.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -77.00pt), (0.00pt, 77.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  bezier((0.00pt, -77.00pt), (66.68pt, 38.50pt), (29.70pt, -17.15pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  content((-33.34pt, -19.25pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no])
  content((41.27pt, -71.49pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove v w])
  content((-54.00pt, 18.48pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[then choose the direction])
  content((97.67pt, -22.51pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[then choose the direction])
  circle((0.00pt, 77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 77.00pt), text(size: 9pt, fill: black)[t])
  circle((66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, 38.50pt), text(size: 9pt, fill: black)[u])
  circle((66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, -38.50pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -77.00pt), text(size: 9pt, fill: black)[w])
  circle((-66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, -38.50pt), text(size: 9pt, fill: black)[x])
  circle((-66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, 38.50pt), text(size: 9pt, fill: black)[y])
  line((-68.56pt, 36.59pt), (-64.18pt, 34.17pt), (-64.09pt, 39.17pt), fill: black, stroke: none, close: true)
  line((-2.58pt, 76.28pt), (0.00pt, 72.00pt), (2.58pt, 76.28pt), fill: black, stroke: none, close: true)
  line((66.91pt, 43.49pt), (66.68pt, 38.50pt), (71.20pt, 40.64pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 77.00pt), (66.68pt, 38.50pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((66.68pt, 38.50pt), (0.00pt, -77.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -77.00pt), (-66.68pt, 38.50pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((-66.68pt, 38.50pt), (-66.68pt, -38.50pt), stroke: 0.7pt + black)
  line((-66.68pt, -38.50pt), (66.68pt, -38.50pt), stroke: 0.7pt + black)
  line((0.00pt, 77.00pt), (0.00pt, -77.00pt), stroke: 0.7pt + black)
  content((33.34pt, -19.25pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove w u])
  content((-58.02pt, -67.38pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[do not remove bridge wy])
  circle((0.00pt, 77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 77.00pt), text(size: 9pt, fill: black)[t])
  circle((66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, 38.50pt), text(size: 9pt, fill: black)[u])
  circle((66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, -38.50pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -77.00pt), text(size: 9pt, fill: black)[w])
  circle((-66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, -38.50pt), text(size: 9pt, fill: black)[x])
  circle((-66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, 38.50pt), text(size: 9pt, fill: black)[y])
  line((67.35pt, 41.09pt), (62.35pt, 41.00pt), (64.78pt, 36.63pt), fill: black, stroke: none, close: true)
  line((-68.56pt, 36.59pt), (-64.18pt, 34.17pt), (-64.09pt, 39.17pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 67.60pt), (58.54pt, 33.80pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 67.60pt), (0.00pt, -67.60pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, -67.60pt), (-58.54pt, 33.80pt), stroke: 0.7pt + black)
  line((-58.54pt, 33.80pt), (-58.54pt, -33.80pt), stroke: 0.7pt + black)
  line((-58.54pt, -33.80pt), (58.54pt, -33.80pt), stroke: 0.7pt + black)
  content((37.20pt, 64.44pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove u t])
  circle((0.00pt, 67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.60pt), text(size: 9pt, fill: black)[t])
  circle((58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, 33.80pt), text(size: 9pt, fill: black)[u])
  circle((58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, -33.80pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -67.60pt), text(size: 9pt, fill: black)[w])
  circle((-58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, -33.80pt), text(size: 9pt, fill: black)[x])
  circle((-58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, 33.80pt), text(size: 9pt, fill: black)[y])
  line((2.58pt, -66.88pt), (0.00pt, -62.60pt), (-2.58pt, -66.88pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 67.60pt), (0.00pt, -67.60pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -67.60pt), (-58.54pt, 33.80pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-58.54pt, 33.80pt), (-58.54pt, -33.80pt), stroke: 0.7pt + black)
  line((-58.54pt, -33.80pt), (58.54pt, -33.80pt), stroke: 0.7pt + black)
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove t w])
  circle((0.00pt, 67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.60pt), text(size: 9pt, fill: black)[t])
  circle((58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, 33.80pt), text(size: 9pt, fill: black)[u])
  circle((58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, -33.80pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -67.60pt), text(size: 9pt, fill: black)[w])
  circle((-58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, -33.80pt), text(size: 9pt, fill: black)[x])
  circle((-58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, 33.80pt), text(size: 9pt, fill: black)[y])
  line((-60.42pt, 31.89pt), (-56.04pt, 29.47pt), (-55.95pt, 34.47pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, -67.60pt), (-58.54pt, 33.80pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-58.54pt, 33.80pt), (-58.54pt, -33.80pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-58.54pt, -33.80pt), (58.54pt, -33.80pt), stroke: 0.7pt + black)
  content((-29.27pt, -16.90pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove w y])
  circle((0.00pt, 67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 67.60pt), text(size: 9pt, fill: black)[t])
  circle((58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, 33.80pt), text(size: 9pt, fill: black)[u])
  circle((58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((58.54pt, -33.80pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -67.60pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -67.60pt), text(size: 9pt, fill: black)[w])
  circle((-58.54pt, -33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, -33.80pt), text(size: 9pt, fill: black)[x])
  circle((-58.54pt, 33.80pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-58.54pt, 33.80pt), text(size: 9pt, fill: black)[y])
  line((-55.97pt, -33.08pt), (-58.54pt, -28.80pt), (-61.12pt, -33.08pt), fill: black, stroke: none, close: true)
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((-66.68pt, 38.50pt), (-66.68pt, -38.50pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-66.68pt, -38.50pt), (66.68pt, -38.50pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  content((-108.20pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[remove y x then x v])
  circle((0.00pt, 77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 77.00pt), text(size: 9pt, fill: black)[t])
  circle((66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, 38.50pt), text(size: 9pt, fill: black)[u])
  circle((66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((66.68pt, -38.50pt), text(size: 9pt, fill: black)[v])
  circle((0.00pt, -77.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -77.00pt), text(size: 9pt, fill: black)[w])
  circle((-66.68pt, -38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, -38.50pt), text(size: 9pt, fill: black)[x])
  circle((-66.68pt, 38.50pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-66.68pt, 38.50pt), text(size: 9pt, fill: black)[y])
  line((65.97pt, -35.92pt), (61.68pt, -38.50pt), (65.97pt, -41.08pt), fill: black, stroke: none, close: true)
})]
)]),
  alt: "Eight graphs. Each graph has six vertices: t, u, v, w, x, and y. In the first graph, the edges are t u, u w, w y, y x, x v, v t, and v w. Text reads, start at odd degree. Choose direction. The edges flowing from t to u, v, and w are highlighted in blue. The second graph is the same as that of the first, with the edge, tv in dashed lines and labeled remove tv. The edges flowing from v to w and x are in blue. Text reads, then choose the direction. The third graph shows edges, t u, u w, w y, y x, x v, and v w. The edge, v w is in dashed lines and labeled remove v w. The edges from w to t and u are in blue and labeled then choose the direction. The edge from w to y is shown in red and labeled no. The fourth graph shows the edges, t u, u w, w y, y x, x v, and t w. The edge, w u is in dashed lines, and remove w u. The edge from w to y is in red and labeled do not remove bridge wy. The edge from u to t is in blue. The fifth graph shows the edge, t u, t w, w y, y x, and x v. The edge, u t is in dashed lines and labeled remove u t. The edge from t to w is in blue. The sixth graph shows the edge, t w, w y, y z, and x v. The edge, t w is in dashed lines and labeled remove t w. The edge from w to y is in blue. The seventh graph shows the edges, w y, y z, and x v. The edge, w y is in dashed lines and labeled remove w y. The edge from y to x is in blue. The eighth graph shows the edges, y x, and x v. The edge, y x is in dashed lines and labeled remove y x then x v. The edge from x to v is in blue.", caption: [Using Fleury’s Algorithm To Find Euler Trail],
)


    The Euler trail that was found in  is #emph[t] → #emph[v] → #emph[w] → #emph[u] → #emph[t] → #emph[w] → #emph[y] → #emph[x] → #emph[v].


    #examplebox("Example 3")[Finding an Euler Trail with Fleury’s Algorithm][
Use Fleury’s Algorithm to find an Euler trail for Graph #emph[J] 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 J])
  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), (41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((41.36pt, 7.29pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (41.36pt, 7.29pt), stroke: 0.7pt + black)
  line((27.00pt, 32.17pt), (-14.36pt, -39.47pt), stroke: 0.7pt + black)
  line((14.36pt, -39.47pt), (-14.36pt, -39.47pt), stroke: 0.7pt + black)
  line((-14.36pt, -39.47pt), (-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: "Graph J has 9 vertices: a, b, c, d, e, f, g, h, and i. Edges connect a b, b d, d c, c a, b c, b f, e f, f g, g i, I h, and h e.", caption: [Graph #emph[J]],
)


      
      #solutionbox[
#strong[Step 1:] Choose one of the two vertices of odd degree, #emph[c] or #emph[f], as your starting vertex. We will choose #emph[c].


        #strong[Step 2:] Remove edge #emph[ca, cb], or #emph[cd]. None of these are cut edges so we can select any of the three. We will choose #emph[cb] as shown in  to be the first edge removed.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 77.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph J])
  line((0.00pt, 56.25pt), (36.16pt, 43.09pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((36.16pt, 43.09pt), (48.72pt, -28.13pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((48.72pt, -28.13pt), (55.40pt, 9.77pt), stroke: 0.7pt + black)
  line((55.40pt, 9.77pt), (0.00pt, 56.25pt), stroke: 0.7pt + black)
  line((36.16pt, 43.09pt), (55.40pt, 9.77pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.16pt, 43.09pt), (-19.24pt, -52.86pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((19.24pt, -52.86pt), (-19.24pt, -52.86pt), stroke: 0.7pt + black)
  line((-19.24pt, -52.86pt), (-48.72pt, -28.13pt), stroke: 0.7pt + black)
  line((-48.72pt, -28.13pt), (-36.16pt, 43.09pt), stroke: 0.7pt + black)
  line((-36.16pt, 43.09pt), (-55.40pt, 9.77pt), stroke: 0.7pt + black)
  line((-55.40pt, 9.77pt), (19.24pt, -52.86pt), stroke: 0.7pt + black)
  content((8.46pt, -4.88pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no!])
  circle((0.00pt, 56.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 56.25pt), text(size: 9pt, fill: black)[a])
  circle((36.16pt, 43.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.16pt, 43.09pt), text(size: 9pt, fill: black)[b])
  circle((55.40pt, 9.77pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((55.40pt, 9.77pt), text(size: 9pt, fill: black)[c])
  circle((48.72pt, -28.13pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((48.72pt, -28.13pt), text(size: 9pt, fill: black)[d])
  circle((19.24pt, -52.86pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((19.24pt, -52.86pt), text(size: 9pt, fill: black)[e])
  circle((-19.24pt, -52.86pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-19.24pt, -52.86pt), text(size: 9pt, fill: black)[f])
  circle((-48.72pt, -28.13pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-48.72pt, -28.13pt), text(size: 9pt, fill: black)[g])
  circle((-55.40pt, 9.77pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-55.40pt, 9.77pt), text(size: 9pt, fill: black)[h])
  circle((-36.16pt, 43.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.16pt, 43.09pt), text(size: 9pt, fill: black)[i])
  line((-14.15pt, -49.20pt), (-14.24pt, -44.20pt), (-18.61pt, -46.62pt), fill: black, stroke: none, close: true)
})]),
  alt: "Graph J has 9 vertices: a, b, c, d, e, f, g, h, and i. Edges connect a b, b d, d c, c a, b c, b f, e f, f g, g i, I h, and h e. The edge, b c is shown in dashed lines. The edges, b d, and b a are in blue. The edge from b to f is in red and labeled no!", caption: [Graph #emph[J] with #emph[cb] Removed],
)


        #strong[Repeat Step 2] The next choice is to remove edge #emph[ba, bd], or #emph[bf] as shown in , but #emph[bf] is not an option since it is a bridge. We will choose #emph[ba] as shown in  to be the second edge removed.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 65.09pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph J])
  line((0.00pt, 44.09pt), (28.34pt, 33.78pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((28.34pt, 33.78pt), (38.18pt, -22.05pt), stroke: 0.7pt + black)
  line((38.18pt, -22.05pt), (43.42pt, 7.66pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((43.42pt, 7.66pt), (0.00pt, 44.09pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((28.34pt, 33.78pt), (-15.08pt, -41.43pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((15.08pt, -41.43pt), (-15.08pt, -41.43pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-15.08pt, -41.43pt), (-38.18pt, -22.05pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-38.18pt, -22.05pt), (-28.34pt, 33.78pt), stroke: 0.7pt + black)
  line((-28.34pt, 33.78pt), (-43.42pt, 7.66pt), stroke: 0.7pt + black)
  line((-43.42pt, 7.66pt), (15.08pt, -41.43pt), stroke: 0.7pt + black)
  content((45.47pt, -8.02pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[4])
  content((41.81pt, 30.42pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[3])
  content((6.63pt, -3.83pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[5])
  content((0.00pt, -47.43pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[6])
  circle((0.00pt, 44.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 44.09pt), text(size: 9pt, fill: black)[a])
  circle((28.34pt, 33.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((28.34pt, 33.78pt), text(size: 9pt, fill: black)[b])
  circle((43.42pt, 7.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.42pt, 7.66pt), text(size: 9pt, fill: black)[c])
  circle((38.18pt, -22.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((38.18pt, -22.05pt), text(size: 9pt, fill: black)[d])
  circle((15.08pt, -41.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((15.08pt, -41.43pt), text(size: 9pt, fill: black)[e])
  circle((-15.08pt, -41.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-15.08pt, -41.43pt), text(size: 9pt, fill: black)[f])
  circle((-38.18pt, -22.05pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-38.18pt, -22.05pt), text(size: 9pt, fill: black)[g])
  circle((-43.42pt, 7.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.42pt, 7.66pt), text(size: 9pt, fill: black)[h])
  circle((-28.34pt, 33.78pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-28.34pt, 33.78pt), text(size: 9pt, fill: black)[i])
})]),
  alt: "Graph J has 9 vertices: a, b, c, d, e, f, g, h, and i. The edges connect a b, b d, d c, c a, b f, e f, f g, g i, I h, and h e. The edge, a b is in dashed lines. The edges from a to c, c to d, b to f, f to e, and f to g are labeled 3, 4, 5, 6, blank, and blank and shaded in blue.", caption: [Graph #emph[J] with #emph[cb] and #emph[ba] Removed],
)


        #strong[Repeat Step 2] for the third, fourth, fifth, sixth, and seventh edges. As shown in , until we get to the seventh edge there is only one option each time, #emph[ac, cd, db], and #emph[bf] in that order. For the seventh edge, we must choose between #emph[fe] and #emph[fg]. Neither of these are bridges. We choose #emph[fe].  shows that #emph[ac, cd, db, bf,] and #emph[fe] have been removed.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 71.17pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph J])
  line((32.25pt, 38.43pt), (43.45pt, -25.09pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((43.45pt, -25.09pt), (49.41pt, 8.71pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((49.41pt, 8.71pt), (0.00pt, 50.17pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((32.25pt, 38.43pt), (-17.16pt, -47.15pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((17.16pt, -47.15pt), (-17.16pt, -47.15pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((17.16pt, -47.15pt), (-49.41pt, 8.71pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-49.41pt, 8.71pt), (-32.25pt, 38.43pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-32.25pt, 38.43pt), (-43.45pt, -25.09pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-43.45pt, -25.09pt), (-17.16pt, -47.15pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  content((-16.13pt, -19.22pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[8])
  content((-45.85pt, 26.47pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[9])
  content((-40.31pt, -7.30pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[10])
  content((-35.28pt, -42.04pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[11])
  circle((0.00pt, 50.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 50.17pt), text(size: 9pt, fill: black)[a])
  circle((32.25pt, 38.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.25pt, 38.43pt), text(size: 9pt, fill: black)[b])
  circle((49.41pt, 8.71pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((49.41pt, 8.71pt), text(size: 9pt, fill: black)[c])
  circle((43.45pt, -25.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.45pt, -25.09pt), text(size: 9pt, fill: black)[d])
  circle((17.16pt, -47.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((17.16pt, -47.15pt), text(size: 9pt, fill: black)[e])
  circle((-17.16pt, -47.15pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-17.16pt, -47.15pt), text(size: 9pt, fill: black)[f])
  circle((-43.45pt, -25.09pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.45pt, -25.09pt), text(size: 9pt, fill: black)[g])
  circle((-49.41pt, 8.71pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-49.41pt, 8.71pt), text(size: 9pt, fill: black)[h])
  circle((-32.25pt, 38.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.25pt, 38.43pt), text(size: 9pt, fill: black)[i])
})]),
  alt: "Graph J has 9 vertices: a, b, c, d, e, f, g, h, and i. The edges connect b d, d c, c a, b f, e f, f g, g i, I h, and h e. The edges, a c, c d, d b, b f, and f e are in dashed lines. The edges, e to h, h to i, i to g, and g to f are shaded in blue and labeled 8, 9, 10, and 11.", caption: [Graph #emph[J] with Seven Edges Removed],
)


        #strong[Repeat Step 2] for the eight, ninth, tenth, and eleventh edges. As shown in , there is only one option for each of these edges, #emph[eh, hi, ig], and #emph[gf], in that order.


        #strong[Step 3:] Write out the Euler trail using the vertices in the sequence that the edges were removed. We removed #emph[cb, ba, ac, cd, db, bf, fe, eh, hi, ig], and #emph[gf], in that order. The Euler trail is #emph[c] → #emph[b] → #emph[a] → #emph[c] → #emph[d] → #emph[b] → #emph[f] → #emph[e] → #emph[h] → #emph[i] → #emph[g] → #emph[f].
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[TIP! To avoid errors, count the number of edges in your graph and make sure that your Euler trail represents that number of edges.]
]


    
    In the previous section, we found Euler circuits using an algorithm that involved joining circuits together into one large circuit. You can also use Fleury’s algorithm to find Euler circuits in any graph with vertices of all even degree. In that case, you can start at any vertex that you would like to use.


    #strong[Step 1:] Begin at any vertex.


    #strong[Step 2:] Remove an edge between the vertex and any adjacent vertex that is NOT a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all edges are removed.


    #strong[Step 3:] Write out the Euler circuit using the sequence of vertices and edges that you found. For example, if you removed #emph[ab, bc, cd, de], and #emph[ea], in that order, then the Euler circuit is #emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[e] → #emph[a].


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Fleurys_algorithm")[Fluery's Algorithm to Find an Euler Circuit]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[IMPORTANT! Since a circuit is a closed trail, every Euler circuit is also an Euler trail, but when we say Euler trail in this chapter, we are referring to an open Euler trail that begins and ends at different vertices.]
]


    #examplebox("Example 4")[Finding an Euler Circuit or Euler Trail Using Fleury’s Algorithm][
Use Fleury’s algorithm to find either an Euler circuit or Euler trail in Graph #emph[G] in .


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  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((54.25pt, 0.00pt), (0.00pt, 54.25pt), stroke: 0.7pt + black)
  line((46.98pt, -27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((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((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  line((-27.12pt, 46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (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), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, -27.12pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (-46.98pt, 27.12pt), 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)[b])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), 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((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[c])
  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((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((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[j])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[k])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[n])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[o])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has three quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The vertices of the second quadrilateral are i, h, j, and k. The vertices of the third quadrilateral are n, m, o, and p. Other edges connect c to d, d to i, i to j, j to n, and n to o. A curved edge connects c and o.", caption: [Graph #emph[G]],
)


      
      #solutionbox[
Graph #emph[G] has all vertices of even degree so it has an Euler circuit.


        #strong[Step 1:] Choose any vertex. We will choose vertex #emph[j].


        #strong[Step 2:] Remove one of the four edges that meet at vertex #emph[j]. Since #emph[jn] is a bridge, we must remove either #emph[jh, ji], or #emph[jk.] We remove #emph[ji] as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 95.34pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, 74.34pt), (37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((37.17pt, 64.38pt), (64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((64.38pt, 37.17pt), (74.34pt, 0.00pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (0.00pt, 74.34pt), stroke: 0.7pt + black)
  line((64.38pt, -37.17pt), (37.17pt, -64.38pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((37.17pt, -64.38pt), (0.00pt, -74.34pt), stroke: 0.7pt + black)
  line((0.00pt, -74.34pt), (-37.17pt, -64.38pt), stroke: 0.7pt + black)
  line((-37.17pt, -64.38pt), (64.38pt, -37.17pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-74.34pt, -0.00pt), stroke: 0.7pt + black)
  line((-74.34pt, -0.00pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((-64.38pt, 37.17pt), (-37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((-37.17pt, 64.38pt), (-64.38pt, -37.17pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((37.17pt, 64.38pt), (64.38pt, -37.17pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((64.38pt, -37.17pt), (0.00pt, -74.34pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -74.34pt), (-64.38pt, -37.17pt), stroke: 0.7pt + black)
  line((-64.38pt, -37.17pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  content((56.76pt, -8.74pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no!])
  circle((0.00pt, 74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 74.34pt), text(size: 9pt, fill: black)[b])
  circle((37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, 64.38pt), text(size: 9pt, fill: black)[d])
  circle((64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, 37.17pt), text(size: 9pt, fill: black)[e])
  circle((74.34pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((74.34pt, 0.00pt), text(size: 9pt, fill: black)[c])
  circle((64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, -37.17pt), text(size: 9pt, fill: black)[i])
  circle((37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, -64.38pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -74.34pt), text(size: 9pt, fill: black)[j])
  circle((-37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, -64.38pt), text(size: 9pt, fill: black)[k])
  circle((-64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, -37.17pt), text(size: 9pt, fill: black)[n])
  circle((-74.34pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-74.34pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, 37.17pt), text(size: 9pt, fill: black)[o])
  circle((-37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, 64.38pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has three quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The vertices of the second quadrilateral are i, h, j, and k. The vertices of the third quadrilateral are n, m, o, and p. Other edges connect c to d, d to i, i to j, j to n, and n to o. A curved edge connects c and o. The edge, i j is in dashed lines. The edges, i h, and i k are in blue. The edge, d i is in red and labeled no!", caption: [Graph #emph[G] with 1 Edge Removed],
)


        #strong[Repeat Step 2:] Since #emph[id] is a bridge, we can remove either #emph[ih] or #emph[ik] next. We remove #emph[ih], and then the only option is to remove #emph[hj] as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 95.34pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, 74.34pt), (37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((37.17pt, 64.38pt), (64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((64.38pt, 37.17pt), (74.34pt, 0.00pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (0.00pt, 74.34pt), stroke: 0.7pt + black)
  line((64.38pt, -37.17pt), (37.17pt, -64.38pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((37.17pt, -64.38pt), (0.00pt, -74.34pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -74.34pt), (-37.17pt, -64.38pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-37.17pt, -64.38pt), (64.38pt, -37.17pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-74.34pt, -0.00pt), stroke: 0.7pt + black)
  line((-74.34pt, -0.00pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((-64.38pt, 37.17pt), (-37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((-37.17pt, 64.38pt), (-64.38pt, -37.17pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((37.17pt, 64.38pt), (64.38pt, -37.17pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, -74.34pt), (-64.38pt, -37.17pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  content((-46.35pt, -47.58pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no!])
  circle((0.00pt, 74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 74.34pt), text(size: 9pt, fill: black)[b])
  circle((37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, 64.38pt), text(size: 9pt, fill: black)[d])
  circle((64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, 37.17pt), text(size: 9pt, fill: black)[e])
  circle((74.34pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((74.34pt, 0.00pt), text(size: 9pt, fill: black)[c])
  circle((64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, -37.17pt), text(size: 9pt, fill: black)[i])
  circle((37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, -64.38pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -74.34pt), text(size: 9pt, fill: black)[j])
  circle((-37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, -64.38pt), text(size: 9pt, fill: black)[k])
  circle((-64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, -37.17pt), text(size: 9pt, fill: black)[n])
  circle((-74.34pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-74.34pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, 37.17pt), text(size: 9pt, fill: black)[o])
  circle((-37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, 64.38pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has three quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The vertices of the second quadrilateral are i, h, j, and k. The vertices of the third quadrilateral are n, m, o, and p. Other edges connect c to d, d to i, j to n, and n to o. A curved edge connects c and o. The edges, i h, and hj are in dashed lines. The edges, j k, k i, and i d are in blue. The edge, j n is in red and labeled no!", caption: [Graph #emph[G] with 3 Edges Removed],
)


        #strong[Repeat Step 2:] Since #emph[jn] is a bridge, the next edge removed must be #emph[jk], and then the only option is to remove #emph[ki] followed by #emph[id] as shown. Even though #emph[id] is a bridge, it can be removed because it is the only option at this point.  shows Graph #emph[G] with these additional edges removed.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, 54.25pt), (27.12pt, 46.98pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((27.12pt, 46.98pt), (46.98pt, 27.12pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((46.98pt, 27.12pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (0.00pt, 54.25pt), stroke: 0.7pt + black)
  line((-46.98pt, -27.12pt), (-54.25pt, -0.00pt), stroke: 0.7pt + black)
  line((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), stroke: 0.7pt + black)
  line((-27.12pt, 46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (27.12pt, 46.98pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((27.12pt, 46.98pt), (46.98pt, -27.12pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  bezier((46.98pt, -27.12pt), (-27.12pt, -46.98pt), (8.84pt, -32.99pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  bezier((46.98pt, -27.12pt), (-27.12pt, -46.98pt), (11.01pt, -41.11pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-27.12pt, -46.98pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((-46.98pt, -27.12pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (-46.98pt, 27.12pt), 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)[b])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), 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((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[c])
  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((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((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[j])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[k])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[n])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[o])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has two quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The other vertices are i, h, j, and k. The vertices of the second quadrilateral are n, m, o, and p. Other edges connect c to d, d to i, i to k, k to j, j to n, and n to o. A curved edge connects c and o. The edges, i k, i k, and i d are in dashed lines. The edges d b, d c, and d e are in blue.", caption: [Graph #emph[G] with 6 Edges Removed],
)


        #strong[Repeat Step 2:] Choose any one of the edges #emph[db, dc], or #emph[de]. We remove #emph[dc] as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 95.34pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((74.34pt, 0.00pt), (0.00pt, 74.34pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((0.00pt, 74.34pt), (37.17pt, 64.38pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((37.17pt, 64.38pt), (64.38pt, 37.17pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((64.38pt, 37.17pt), (74.34pt, 0.00pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (37.17pt, 64.38pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -74.34pt), (-64.38pt, -37.17pt), stroke: 0.7pt + black)
  line((-64.38pt, -37.17pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((74.34pt, 0.00pt), (-64.38pt, 37.17pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-74.34pt, -0.00pt), stroke: 0.7pt + black)
  line((-74.34pt, -0.00pt), (-64.38pt, 37.17pt), stroke: 0.7pt + black)
  line((-64.38pt, 37.17pt), (-37.17pt, 64.38pt), stroke: 0.7pt + black)
  line((-37.17pt, 64.38pt), (-64.38pt, -37.17pt), stroke: 0.7pt + black)
  content((4.98pt, 18.58pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no!])
  circle((0.00pt, 74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 74.34pt), text(size: 9pt, fill: black)[b])
  circle((37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, 64.38pt), text(size: 9pt, fill: black)[d])
  circle((64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, 37.17pt), text(size: 9pt, fill: black)[e])
  circle((74.34pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((74.34pt, 0.00pt), text(size: 9pt, fill: black)[c])
  circle((64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, -37.17pt), text(size: 9pt, fill: black)[i])
  circle((37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, -64.38pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -74.34pt), text(size: 9pt, fill: black)[j])
  circle((-37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, -64.38pt), text(size: 9pt, fill: black)[k])
  circle((-64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, -37.17pt), text(size: 9pt, fill: black)[n])
  circle((-74.34pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-74.34pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, 37.17pt), text(size: 9pt, fill: black)[o])
  circle((-37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, 64.38pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has two quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The other vertices are i, h, j, and k. The vertices of the second quadrilateral are n, m, o, and p. Other edges connect c to d, j to n, and n to o. A curved edge connects c and o. The edge, c d is in dashed lines. The edges, c b, b d, and d e are in blue. The edge c to o is in red and is labeled no!", caption: [Graph #emph[G] with 7 Edges Removed],
)


        #strong[Repeat Step 2:] Since #emph[co] is a bridge, choose #emph[cb] next. We remove #emph[cb], then #emph[bd], and then #emph[de] as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, 54.25pt), (27.12pt, 46.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((27.12pt, 46.98pt), (46.98pt, 27.12pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((46.98pt, 27.12pt), (54.25pt, 0.00pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (0.00pt, 54.25pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((46.98pt, -27.12pt), (27.12pt, -46.98pt), stroke: 0.7pt + black)
  line((27.12pt, -46.98pt), (0.00pt, -54.25pt), stroke: 0.7pt + black)
  line((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)
  bezier((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), (-46.56pt, 12.47pt), stroke: 0.7pt + black)
  bezier((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), (-34.08pt, 34.08pt), stroke: 0.7pt + black)
  line((-27.12pt, 46.98pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: 0.7pt + black)
  bezier((-46.98pt, -27.12pt), (-46.98pt, 27.12pt), (-42.78pt, -0.00pt), stroke: 0.7pt + black)
  line((54.25pt, 0.00pt), (-46.98pt, 27.12pt), stroke: 0.7pt + black)
  bezier((-46.98pt, 27.12pt), (-54.25pt, -0.00pt), (-46.56pt, 12.47pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  bezier((-46.98pt, 27.12pt), (-46.98pt, -27.12pt), (-42.78pt, -0.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  bezier((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), (-40.02pt, 40.02pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 54.25pt), text(size: 9pt, fill: black)[b])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), 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((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[c])
  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((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((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[j])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[k])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[n])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[o])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has two quadrilaterals. The vertices of the first quadrilateral are b, d, e, and c. The other vertices are i, h, j, and k. The vertices of the second quadrilateral are n, m, o, and p. Other edges connect j to n, and n to o. A curved edge connects c and o. The edges, c b, b d, and d e are in dashed lines. The edges, e to c, c to o, o to m, o to n, and o to p are in blue.", caption: [Graph #emph[G] with 10 Edges Removed],
)


        #strong[Repeat Step 2:] Next, remove #emph[ec] and #emph[co]. Then choose any of #emph[op, pn], or #emph[om]. We remove on as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 95.34pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, -74.34pt), (-64.38pt, -37.17pt), stroke: (paint: rgb("#d62128"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-64.38pt, 37.17pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((74.34pt, 0.00pt), (-64.38pt, 37.17pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((74.34pt, 0.00pt), (64.38pt, 37.17pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-64.38pt, -37.17pt), (-74.34pt, -0.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-64.38pt, -37.17pt), (-37.17pt, 64.38pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  content((-18.03pt, -63.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[no!])
  circle((0.00pt, 74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 74.34pt), text(size: 9pt, fill: black)[b])
  circle((37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, 64.38pt), text(size: 9pt, fill: black)[d])
  circle((64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, 37.17pt), text(size: 9pt, fill: black)[e])
  circle((74.34pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((74.34pt, 0.00pt), text(size: 9pt, fill: black)[c])
  circle((64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((64.38pt, -37.17pt), text(size: 9pt, fill: black)[i])
  circle((37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((37.17pt, -64.38pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -74.34pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -74.34pt), text(size: 9pt, fill: black)[j])
  circle((-37.17pt, -64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, -64.38pt), text(size: 9pt, fill: black)[k])
  circle((-64.38pt, -37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, -37.17pt), text(size: 9pt, fill: black)[n])
  circle((-74.34pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-74.34pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-64.38pt, 37.17pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-64.38pt, 37.17pt), text(size: 9pt, fill: black)[o])
  circle((-37.17pt, 64.38pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-37.17pt, 64.38pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has one quadrilateral. The vertices are b, d, e, c, i, h, j, and k. The vertices of the second quadrilateral are n, m, o, and p. Other edges connect j to n, and n to o. A curved edge connects c and o. The edges, n o, c e, and co are in dashed lines. The edges, n m, and n p are in blue. The edge, n j is in red and labeled no!", caption: [Graph #emph[G] with 13 Edges Removed],
)


        #strong[Repeat Step 2:] Next, remove either #emph[nm], #emph[np], or #emph[nj], but #emph[nj] is a So, we remove #emph[nm] as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 75.25pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, -54.25pt), (-46.98pt, -27.12pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-46.98pt, -27.12pt), (-54.25pt, -0.00pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt, dash: "dashed"))
  line((-54.25pt, -0.00pt), (-46.98pt, 27.12pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-46.98pt, 27.12pt), (-27.12pt, 46.98pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  line((-27.12pt, 46.98pt), (-46.98pt, -27.12pt), stroke: (paint: rgb("#1d56a6"), thickness: 0.7pt))
  circle((0.00pt, 54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 54.25pt), text(size: 9pt, fill: black)[b])
  circle((27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((27.12pt, 46.98pt), 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((54.25pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((54.25pt, 0.00pt), text(size: 9pt, fill: black)[c])
  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((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((0.00pt, -54.25pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -54.25pt), text(size: 9pt, fill: black)[j])
  circle((-27.12pt, -46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, -46.98pt), text(size: 9pt, fill: black)[k])
  circle((-46.98pt, -27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, -27.12pt), text(size: 9pt, fill: black)[n])
  circle((-54.25pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-54.25pt, -0.00pt), text(size: 9pt, fill: black)[m])
  circle((-46.98pt, 27.12pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-46.98pt, 27.12pt), text(size: 9pt, fill: black)[o])
  circle((-27.12pt, 46.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-27.12pt, 46.98pt), text(size: 9pt, fill: black)[p])
})]),
  alt: "Graph G has one quadrilateral. The vertices are b, d, e, c, i, h, j, and k. The vertices of the quadrilateral are n, m, o, and p. An edge connects j to n. The edge, n m is in dashed lines. The edges, m o, o p, p n, and n j are in blue.", caption: [Graph #emph[G] with 14 Edges Removed],
)


        #strong[Repeat Step 2:] Next, remove #emph[mo, op, pn], and #emph[nj]. And we are done!


        #strong[Step 3:] Notice that the algorithm brought us back to the vertex where we started, forming an Euler circuit. Write out the Euler circuit:


        #emph[j] → #emph[i] → #emph[h] → #emph[j] → #emph[k] → #emph[i] → #emph[d] → #emph[c] → #emph[b] → #emph[d] → #emph[e] → #emph[c] → #emph[o] → #emph[n] → #emph[m] → #emph[o] → #emph[p] → #emph[n] → #emph[j]
]
]


    
    #notebox("Work It Out", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
We have discussed a lot of subtle concepts in this section. Let’s make sure we are all on the same page. Work with a partner to explain why each of the following facts about bridges are true. Support your explanations with definitions and graphs.


      + When a bridge is removed from a graph, the number of components increases.
+ A bridge is never part of a circuit.
+ An edge that is part of a triangle is never a local bridge.
]


  
  
  
  
    
=== Key Terms


    - algorithm
- Fleury’s algorithm
- Euler trail
- bridge
- local bridge


  
  
    
=== Key Concepts


    - An Euler trail exists whenever a graph has exactly two vertices of odd degree.
- When a bridge is removed from a graph, the number of components increases.
- A bridge is never part of a circuit.
- When a local bridge is removed from a graph, the distance between vertices increases.
- An edge that is part of a triangle is never a local bridge.


  
  
    
=== Videos


    - #link("https://openstax.org/r/bridges_local_bridges")[Bridges and Local Bridges in Graph Theory]
- #link("https://openstax.org/r/Fleurys_algorithm")[Fluery's Algorithm to Find an Euler Circuit]