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

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

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

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

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

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

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

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

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


  
== 12.3#h(0.6em)Comparing Graphs


  #figure(figph[A map of the world continents. The continents are North America, South America, Europe, Asia, Africa, Oceania, and Antarctica.], alt: "A map of the world continents. The continents are North America, South America, Europe, Asia, Africa, Oceania, and Antarctica.", caption: [A flat map represents the surface of Earth in two dimensions.])


  #figure(figph[A globe.], alt: "A globe.", caption: [A globe represents the surface of Earth in three dimensions.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Identify the characteristics used to compare graphs.
+ Determine when two graphs represent the same relationships
+ Explore real-world examples of graph isomorphisms
+ Find the complement of a graph


  
  Maps of the same region may not always look the same. For example, a map of Earth on a flat surface looks distorted at the poles. When the same regions are mapped on a spherical globe, the countries that are closer to the polls appear smaller without the distortion. Despite these differences, the two maps still communicate the same relationships between nations such as shared boundaries, and relative position on the earth. In essence, they are the same map. This means that for every point on one map, there is a corresponding point on the other map in the same relative location. In this section, we will determine exactly what characteristics need to be the shared by two graphs in order for us to consider them “the same.”


  
    
=== When Are Two Graphs Really the Same Graph?


    In arithmetic, when two numbers have the same value, we say they are equal, like ½ = 0.5. Although ½ and 0.5 look different, they have the same value, because they are assigned the same position on the real number line. When do we say that two graphs are equal?


    shows Graphs #emph[A] and #emph[F], which are identical except for the labels. Graphs are visual representations of connections. As long as two graphs indicate the same pattern of connections, like Graph #emph[A] and Graph #emph[F], they are considered to be equal, or in graph theory terms, #strong[isomorphic].


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.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((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph F])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[g])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[i])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[j])
})]
)]),
  alt: "Two graphs are labeled graph A and graph F. Graph A has four vertices: b, c, d, and e. The edges connect b c, c e, e d, d b, and d c. Graph F has four vertices: g, h, i, and j. The edges connect g h, h j, j i, I g, and I h.", caption: [Identical Graphs with Different Labels],
)


    Two graphs are isomorphic if either one of these conditions holds:


    + One graph can be transformed into the other without breaking existing connections or adding new ones.
+ There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.


    It is important to note that if either one of the isomorphic conditions holds, then both of them do. When we need to decide if two graphs are isomorphic, we will need to make sure that one of them holds. For example,  shows how Graph #emph[T] can be bent and flipped to look like Graph #emph[Z], which means that Graphs #emph[T] and #emph[Z] satisfy condition 1 and are isomorphic.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 81.70pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 60.70pt), anchor: "south", text(size: 9pt)[first])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((49.00pt, 0.00pt), anchor: "west", text(size: 9pt)[second])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -60.70pt), anchor: "north", text(size: 9pt)[third])
  circle((-42.00pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-49.00pt, -0.00pt), anchor: "east", text(size: 9pt)[fourth])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 81.70pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph Z])
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 60.70pt), anchor: "south", text(size: 9pt)[first])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((49.00pt, 0.00pt), anchor: "west", text(size: 9pt)[second])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -60.70pt), anchor: "north", text(size: 9pt)[third])
  circle((-42.00pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-49.00pt, -0.00pt), anchor: "east", text(size: 9pt)[fourth])
})]
)]),
  alt: "Graph T is converted into Graph Z. Edges from the third vertex in graph T connect to the first, second, and fourth vertices. The first and second vertices are connected by an edge. The fourth vertex is moved to the top. Then the whole graph is rotated 180 degrees to achieve graph Z.", caption: [Graph #emph[T] Transformed Into Graph #emph[Z]],
)


    Also, notice that the vertices that were adjacent in the first graph are still adjacent in the transformed graph as shown. For example, vertex 3 is still adjacent to vertex 4, which means they are still neighboring vertices joined by a single edge.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 81.70pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph T])
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 60.70pt), anchor: "south", text(size: 9pt)[first])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((49.00pt, 0.00pt), anchor: "west", text(size: 9pt)[second])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -60.70pt), anchor: "north", text(size: 9pt)[third])
  circle((-42.00pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-49.00pt, -0.00pt), anchor: "east", text(size: 9pt)[fourth])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 81.70pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph Z])
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 60.70pt), anchor: "south", text(size: 9pt)[first])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((49.00pt, 0.00pt), anchor: "west", text(size: 9pt)[second])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -60.70pt), anchor: "north", text(size: 9pt)[third])
  circle((-42.00pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-49.00pt, -0.00pt), anchor: "east", text(size: 9pt)[fourth])
})]
)]),
  alt: "Graph T is converted into Graph Z. Edges from the third vertex in graph T connect to the first, second, and fourth vertices. The first and second vertices are connected by an edge. The fourth vertex is moved to the top. Then the whole graph is rotated 180 degrees to achieve graph Z.", caption: [Adjacent Vertices Are Still Adjacent],
)


  
  
    
=== When Are Two Graphs Really Different?


    Verifying that two graphs are isomorphic can be a challenging process, especially for larger graphs. It makes sense to check for any obvious ways in which the graphs might differ so that we don’t spend time trying to verify that graphs are isomorphic when they are not. If two graphs have any of the differences shown in , then they cannot be isomorphic.


    #figure(table(
  columns: 2, align: left, inset: 6pt,
  table.header([Unequal number of vertices], []),
  [Unequal number of edges], [],
  [Unequal number of vertices of a particular degree], [],
  [Different cyclic subgraphs], [],
))


  
  
    
=== Recognizing Isomorphic Graphs


    Isomorphic graphs that represent the same pattern of connections can look very different despite having the same underlying structure. The edges can be stretched and twisted. The graph can be rotated or flipped. For example, in , each of the diagrams represents the same pattern of connections.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A 1])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[1])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[3])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[4])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A 2])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[1])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[3])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[4])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A 3])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[1])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[3])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[4])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A 4])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[1])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[2])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[3])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[4])
})]
)]),
  alt: "Four representations of the same graph are displayed. The graphs are labeled graph A 1, graph A 2, graph A 3, and graph A 4. In the first graph, the four vertices are connected by edges to resemble a square. The bottom-left and top-right vertices are connected using an edge. The other graph represents the same in different forms.", caption: [Four Representations of the Same Graph],
)


    Looking at , how can we know that these graphs are isomorphic? We will start by checking for any obvious differences. Each of the graphs in  has four vertices and five edges; so, there are no differences there. Next, we will focus on the degrees of the vertices, which have been labeled in .


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[A 1])
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  circle((-42.00pt, 13.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[2])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[A 2])
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  circle((-42.00pt, 13.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[2])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[A 3])
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  circle((-42.00pt, 13.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[2])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[A 4])
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((0.00pt, -42.00pt), (-42.00pt, -0.00pt), (-22.65pt, -22.65pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-16.05pt, -16.05pt), stroke: 0.7pt + black)
  circle((-42.00pt, 13.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[2])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[3])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[2])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[3])
})]
)]),
  alt: "Four representations of the same graph are displayed. The graphs are labeled graph A 1, graph A 2, graph A 3, and graph A 4. In the first graph, the four vertices are connected by edges to resemble a square. The bottom-left and top-right vertices are connected using an edge. The top-left, top-right, bottom-right, and bottom-left vertices are 2, 3, 2, and 3. The other graph represents the same in different forms.", caption: [Graphs with Vertices of the Same Degrees],
)


    As shown in , each graph has two vertices of degree 2 and two vertices of degree 3; so, there are no differences there. Now, let’s check for cyclic subgraphs. These are highlighted in .


    #figure(
  stdfig([#grid(columns: 3, gutter: 1.5em,
  [#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 174.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[First row: two squares, a quadrilateral, and a pentagon])
  line((20.00pt, 20.00pt), (20.00pt, 80.00pt), (80.00pt, 80.00pt), (80.00pt, 20.00pt), close: true, fill: rgb("#d3e1f5"), stroke: 0.7pt + black)
  line((100.00pt, 20.00pt), (100.00pt, 80.00pt), (160.00pt, 80.00pt), (160.00pt, 20.00pt), close: true, fill: rgb("#d3e1f5"), stroke: 0.7pt + black)
  line((20.00pt, 100.00pt), (60.00pt, 140.00pt), (100.00pt, 100.00pt), (80.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((120.00pt, 100.00pt), (140.00pt, 140.00pt), (180.00pt, 100.00pt), (160.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 114.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[Second row: a triangle and three other shapes])
  line((20.00pt, 20.00pt), (60.00pt, 20.00pt), (40.00pt, 80.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((80.00pt, 20.00pt), (120.00pt, 20.00pt), (120.00pt, 60.00pt), (80.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((140.00pt, 20.00pt), (180.00pt, 20.00pt), (180.00pt, 60.00pt), (140.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 114.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[Third row: a triangle and three other shapes])
  line((20.00pt, 20.00pt), (60.00pt, 20.00pt), (40.00pt, 80.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((80.00pt, 20.00pt), (120.00pt, 20.00pt), (120.00pt, 60.00pt), (80.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
  line((140.00pt, 20.00pt), (180.00pt, 20.00pt), (180.00pt, 60.00pt), (140.00pt, 60.00pt), close: true, fill: none, stroke: 0.7pt + black)
})]
)]),
  alt: "Four representations of the same graph are displayed three times. In the first row, two squares, a quadrilateral, and a pentagon are highlighted. In the second row, a triangle and three other shapes are highlighted. In the third row, a triangle and three other shapes are highlighted.", caption: [Graphs with the Same Cyclic Subgraphs],
)


    As shown in , each graph has two triangles and one quadrilateral; so, no differences there either. It is beginning to look likely that these graphs are isomorphic, but we will have to look further to be sure.


    To know with certainty that these graphs are isomorphic, we need to confirm one of the two conditions from the definition of isomorphic graphs. With smaller graphs, you may be able to visualize how to stretch and twist one graph to get the other to see if condition 1 holds. Imagine the edges are stretchy and picture how to pull and twist one graph to form the other. If you can do this without breaking or adding any connections, then the graphs are really the same.  demonstrates how to change graph #emph[A]#sub[4] to get #emph[A]#sub[3], graph #emph[A]#sub[3] to get #emph[A]#sub[2], and graph #emph[A]#sub[2] to get #emph[A]#sub[1].


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 4])
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[TL])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[TR])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[BL])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[BR])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 3])
  line((0.00pt, 42.00pt), (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)[TL])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[TR])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[BL])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[BR])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 2])
  line((0.00pt, 42.00pt), (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)[TL])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[TR])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[BL])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[BR])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A 1])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[TL])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[TR])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[BL])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[BR])
})]
)]),
  alt: "Transformation of Graph A 4 to graph A 1 through graph A 3 and graph A 2. Graph A 4 has four vertices. It resembles a pentagon with a curved edge from the top-left vertex to the bottom-left vertex. The top-right vertex is moved to the center to obtain graph A 3. In graph A 3, the center vertex is moved to the top-left to obtain graph A 2. In graph A 2, the curved edge from the bottom-left vertex to the top-right vertex is shifted inside the graph to obtain graph A 1. In graph A 1, the four vertices are in four corners and they are connected using edges to resemble a square. A diagonal edge from the bottom-left vertex connects to the top-right vertex.", caption: [Transforming Graphs],
)


    Now that we have used visual analysis to see that condition 1 holds for graphs #emph[A]#sub[1], #emph[A]#sub[2], #emph[A]#sub[3], and #emph[A]#sub[4] in , we know that they are isomorphic. In , one of the edges of graph #emph[A]#sub[4] crossed another edge of the graph. By transforming it into graph #emph[A]#sub[3], we have “untangled” it. Graphs that can be untangled are called #strong[planar] graphs. The complete graph with five vertices is an example of a #strong[nonplanar] graph-that means that, no matter how hard you try, you can’t untangle it. But, when you try to figure out if two graphs are the same, it can be helpful to untangle them as much as possible to make the similarities and differences more obvious.


    #examplebox("Example 1")[Identifying Isomorphic Graphs][
Which of the three graphs in  are isomorphic, if any? Justify your answer.


        #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 98.80pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph B 1])
  line((0.00pt, 53.80pt), (53.80pt, 0.00pt), stroke: 0.7pt + black)
  line((53.80pt, 0.00pt), (0.00pt, -53.80pt), stroke: 0.7pt + black)
  line((0.00pt, 53.80pt), (0.00pt, -53.80pt), stroke: 0.7pt + black)
  line((53.80pt, 0.00pt), (-53.80pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 53.80pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 72.50pt), anchor: "south", text(size: 9pt)[top-left])
  circle((53.80pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((60.80pt, 0.00pt), anchor: "west", text(size: 9pt)[bottom-left])
  circle((0.00pt, -53.80pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -72.50pt), anchor: "north", text(size: 9pt)[bottom-right])
  circle((-53.80pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-60.80pt, -0.00pt), anchor: "east", text(size: 9pt)[top-right])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 104.83pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph B 2])
  line((0.00pt, 57.33pt), (57.33pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 57.33pt), (0.00pt, -57.33pt), stroke: 0.7pt + black)
  line((0.00pt, 57.33pt), (-57.33pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -57.33pt), (-57.33pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 57.33pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 76.03pt), anchor: "south", text(size: 9pt)[bottom-center])
  circle((57.33pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((64.33pt, 0.00pt), anchor: "west", text(size: 9pt)[bottom-right])
  circle((0.00pt, -57.33pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -76.03pt), anchor: "north", text(size: 9pt)[bottom-left])
  circle((-57.33pt, -0.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-57.33pt, -0.00pt), text(size: 9pt, fill: black)[top])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 104.83pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph B 3])
  line((0.00pt, 57.33pt), (57.33pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 57.33pt), (0.00pt, -57.33pt), stroke: 0.7pt + black)
  line((-57.33pt, -0.00pt), (0.00pt, -57.33pt), stroke: 0.7pt + black)
  line((-57.33pt, -0.00pt), (57.33pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 57.33pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 57.33pt), text(size: 9pt, fill: black)[top])
  circle((57.33pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((64.33pt, 0.00pt), anchor: "west", text(size: 9pt)[bottom-left])
  circle((0.00pt, -57.33pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -76.03pt), anchor: "north", text(size: 9pt)[bottom-right])
  circle((-57.33pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-64.33pt, -0.00pt), anchor: "east", text(size: 9pt)[bottom-center])
})]
)]),
  alt: "Three graphs are labeled graph B 1, graph B 2, and graph B 3. Graph B 1 has four vertices. Edges connect the top-left and bottom-left vertices, bottom-left and bottom-right vertices, top-left and bottom-right vertices, and bottom-left and top-right vertices. Graph B 2 has four vertices. Edges connect the bottom-center and bottom-right vertices, bottom-center and bottom-left vertices, bottom-center and top vertices, and bottom-left and top vertices. Graph B 3 has four vertices. Edges connect the top vertex with the bottom-left and bottom-right vertices. Edges connect the bottom-center and bottom-right vertices and bottom-center and bottom-left vertices.", caption: [Three Similar Graphs],
)


      
      #solutionbox[
#strong[Step 1:] Check for differences in number of vertices, number of edges, degrees of vertices, and types of cycles to see if an isomorphism is possible.


        - Vertices: They all have the same number of vertices, 4.
- Edges: They all have the same number of edges, 4.
- Degrees: Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2] each have a vertex of degree 3, while Graph #emph[B]#sub[3] does not. So, Graph #emph[B]#sub[3] is not isomorphic to either of the other two graphs, but Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2] could possibly be isomorphic.
- Cycles: Focus on any cycles in Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2]. Each graph has a triangle as shown.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 87.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph B 1])
  line((0.00pt, 0.00pt), (42.00pt, 0.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((0.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((42.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, 11.67pt), anchor: "south-east", text(size: 9pt)[top-left])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, 11.67pt), anchor: "south-west", text(size: 9pt)[bottom-left])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, -53.67pt), anchor: "north-east", text(size: 9pt)[bottom-right])
  circle((42.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, -53.67pt), anchor: "north-west", text(size: 9pt)[top-right])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 89.50pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph B 2])
  line((0.00pt, 0.00pt), (42.00pt, 0.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((0.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((0.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((0.00pt, -42.00pt), (42.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, 11.67pt), anchor: "south-east", text(size: 9pt)[bottom-center])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, 11.67pt), anchor: "south-west", text(size: 9pt)[bottom-right])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, -53.67pt), anchor: "north-east", text(size: 9pt)[bottom-left])
  circle((42.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, -42.00pt), text(size: 9pt, fill: black)[top])
})]
)]),
  alt: "Two graphs are labeled graph B 1 and graph B 2. Graph B 1 has four vertices. Edges connect the top-left and bottom-left vertices, bottom-left and bottom-right vertices, top-left and bottom-right vertices, and bottom-left and top-right vertices. Graph B 2 has four vertices. Edges connect the bottom-center and bottom-right vertices, bottom-center and bottom-left vertices, bottom-center and top vertices, and bottom-left and top vertices. Three edges are highlighted in both graphs.", caption: [Cycles of Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2]],
)


        #strong[Step 2:] If no differences were found and an isomorphism is possible, verify one of the conditions in the definition of isomorphic.


        Since we were able to determine that Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2] have no obvious differences, and they are relatively small graphs, we will attempt to transform one graph into the other, which would verify condition 1. Graph #emph[B]#sub[1] can be transformed into Graph #emph[B]#sub[2] without breaking or adding connections as shown. Begin by untangling graph #emph[B]#sub[1]. Then rotate or flip as needed to see that the graphs match.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 87.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph B 1])
  line((0.00pt, 0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, 11.67pt), anchor: "south-east", text(size: 9pt)[top-left])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, 11.67pt), anchor: "south-west", text(size: 9pt)[bottom-left])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, -53.67pt), anchor: "north-east", text(size: 9pt)[bottom-right])
  circle((42.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, -53.67pt), anchor: "north-west", text(size: 9pt)[top-right])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 87.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph B 2])
  line((0.00pt, 0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (42.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, 11.67pt), anchor: "south-east", text(size: 9pt)[top-left])
  circle((42.00pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, 11.67pt), anchor: "south-west", text(size: 9pt)[bottom-left])
  circle((0.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-14.59pt, -53.67pt), anchor: "north-east", text(size: 9pt)[bottom-right])
  circle((42.00pt, -42.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((56.59pt, -53.67pt), anchor: "north-west", text(size: 9pt)[top-right])
})]
)]),
  alt: "Graph B 1 is converted into graph B 2. Graph B 1 has four vertices. Edges connect the top-left and bottom-left vertices, bottom-left and bottom-right vertices, top-left and bottom-right vertices, and bottom-left and top-right vertices. The last edge is highlighted. It is rotated 90 degrees counterclockwise. Then the graph is rotated 180 degrees clockwise to obtain graph B 2.", caption: [Transformation of Graph #emph[B]#sub[1]],
)


        So, Graph #emph[B]#sub[1] and Graph #emph[B]#sub[2] have the same structure and are isomorphic.
]
]


    
    Have you ever noticed that many popular board games may look different but are really the same game? A good example is the many variations of the board game #emph[Monopoly]®, which was submitted to the U.S. Patent Office in 1935. Although the rules have been revised a bit, a very similar game board is still in use today. There have been many versions of Monopoly over the years. Many have been stylized to reflect a popular theme, such as a show or sports team, while retaining the same game board structure. If we were to represent these different versions of the game using a graph, we would find that the graphs are isomorphic.   . Let's analyze some game boards using graph theory to determine if they have the same structure despite having different appearances.


    #figure(figph[Two game boards and a spinner. The first game board is titled, Colors Game Figure A. It has 12 spaces arranged in a square. The spaces are as follows: A (yellow), B (red), C (green), D (yellow), E (blue), F (blue), G (green), H (purple), I (red), J (purple), K (white), L (white). Arrows show a path starting in space L and moving counterclockwise around the board to end in space L. The second game board is titled, Clock Game Figure B. It has 12 spaces arranged in a circle. The spaces are as follows: I (plus 3), II (plus 7), III (plus 4), IV (minus 3), V (plus 1), VI (minus 1), VII (minus 4), VIII (plus 2), IX (minus 7), X (minus 2), XI (plus 0), XII (minus 0). The space XII is indicated as the start and end space. A spinner has 2 sections labeled 1 and 2.], alt: "Two game boards and a spinner. The first game board is titled, Colors Game Figure A. It has 12 spaces arranged in a square. The spaces are as follows: A (yellow), B (red), C (green), D (yellow), E (blue), F (blue), G (green), H (purple), I (red), J (purple), K (white), L (white). Arrows show a path starting in space L and moving counterclockwise around the board to end in space L. The second game board is titled, Clock Game Figure B. It has 12 spaces arranged in a circle. The spaces are as follows: I (plus 3), II (plus 7), III (plus 4), IV (minus 3), V (plus 1), VI (minus 1), VII (minus 4), VIII (plus 2), IX (minus 7), X (minus 2), XI (plus 0), XII (minus 0). The space XII is indicated as the start and end space. A spinner has 2 sections labeled 1 and 2.", caption: [Two Game Boards])


    #examplebox("Example 2")[Deciding If Graphs are Isomorphic][
A teacher uses games to teach her students about colors and numbers as shown.


        In the Colors Game, shown in Figure #emph[A], each player begins in the space marked START and proceeds in a counterclockwise direction. On each turn, the player spins a spinner marked 1 and 2 and moves forward the number of spaces shown on the spinner.  If the player lands on a space marked with any color other than white, the player must move forward or back to the other space of the same color. The first player to land in or pass the space marked END wins.


        In the Clock Game, shown in Figure #emph[B], each player begins in the space marked START and proceeds in a clockwise direction. On each turn, the player spins a spinner marked 1 and 2 and moves forward the number of spaces shown on the spinner. In the same turn, the player must read the number in the space and move forward the number of spaces indicated by a positive value or backward the number of spaces indicated by a negative value. Then the turn ends.  The first player to land in or pass the space marked END wins.


        Draw a graph or multigraph to represent each game in which the vertices are the spaces and the edges represent the ability of a player to move between the spaces either by a spin or as dictated by a marked color or number. (We will ignore the direction of motion for simplicity.) Transform one of the graphs to show that it is isomorphic to the other and explain what this tells you about the games.


      
      #solutionbox[
The graph representing the Clock Game can be transformed as shown in  so that we can see that the graphs are isomorphic. There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.


        #figure(figph[Six graphs. The first graph is labeled Colors Game Graph. It has 12 vertices arranged in a square, with 3 vertices on each side. A purple line connects the first and third vertices on the top. A red line connects the second vertex on the top with the first vertex on the bottom. A dark green line connects the first vertex on the right side with the second vertex on the bottom. A blue line connects the second and third vertices on the right side. A light green line connects the third vertex on the bottom and the third vertex on the left side. Lines connect each vertex with the vertices two spots to the right and two spots to the left of it. The second graph is labeled Clock Game Graph. It has 12 vertices arranged in a circle. A light green line connects the first and fourth vertices. A red line connects the second and ninth vertices. A dark green line connects the third and seventh vertices. A blue line connects the fifth and sixth vertices. A purple line connects the eighth and tenth vertices. Lines connect each vertex with the vertices two spots to the right and two spots to the left of it. The third graph is the same as the Clock Game Graph. An arrow points to the fourth graph, which shows the Clock Game Graph rotated clockwise so the lines appear three vertices to the right of their original location. An arrow points to the fifth graph, which shows the rotated Clock Game Graph flipped horizontally so it is a mirror image of the previous graph. A double-sided arrow connects the fifth graph and the sixth graph, which is the Colors Game Graph, to show the two graphs now match.], alt: "Six graphs. The first graph is labeled Colors Game Graph. It has 12 vertices arranged in a square, with 3 vertices on each side. A purple line connects the first and third vertices on the top. A red line connects the second vertex on the top with the first vertex on the bottom. A dark green line connects the first vertex on the right side with the second vertex on the bottom. A blue line connects the second and third vertices on the right side. A light green line connects the third vertex on the bottom and the third vertex on the left side. Lines connect each vertex with the vertices two spots to the right and two spots to the left of it. The second graph is labeled Clock Game Graph. It has 12 vertices arranged in a circle. A light green line connects the first and fourth vertices. A red line connects the second and ninth vertices. A dark green line connects the third and seventh vertices. A blue line connects the fifth and sixth vertices. A purple line connects the eighth and tenth vertices. Lines connect each vertex with the vertices two spots to the right and two spots to the left of it. The third graph is the same as the Clock Game Graph. An arrow points to the fourth graph, which shows the Clock Game Graph rotated clockwise so the lines appear three vertices to the right of their original location. An arrow points to the fifth graph, which shows the rotated Clock Game Graph flipped horizontally so it is a mirror image of the previous graph. A double-sided arrow connects the fifth graph and the sixth graph, which is the Colors Game Graph, to show the two graphs now match.", caption: [Graphs for Clock Game and Colors Game])


        This tells us that the games are essentially the same game with the same moves even though the games appear to be different.
]
]


    
    #notebox("People in Mathematics", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Elizabeth Magie]


      Game designer, engineer, comedian, and political activist, Elizabeth Magie designed a game called “Landlord’s Game” to educate fellow citizens about the dangers of monopolies and the benefits of wealth redistribution through a land tax. Magie, whose father had campaigned with Abraham Lincoln, was a proponent of a land tax, an idea popularized by Henry George’s 1879 book, #emph[Progress and Poverty]. She designed the game to be played by two sets of rules for comparison. In one version, the goal was to dominate opponents by creating monopolies, leaving one wealthy player standing in the end. In the other version, all the players were rewarded when a monopoly was created through a simulated land tax. She patented this game for the first time in 1904. Does the game board in  look familiar?


      #figure(figph[The patent for Landloard's Game shows a sketch drawing of the game board.], alt: "The patent for Landloard's Game shows a sketch drawing of the game board.", caption: [#emph[Landlord’s Game] Patent])


      That’s right! A modified version of the game was obtained from friends by a man named Charles Darrow who renamed it Monopoly and sold to Parker Brothers. Parker Brothers later paid Magie \$500 for the right to her patent on it. The property tax version was left behind, and the modern game of Monopoly was born. (Mary Pilon, #emph[Monopoly’s Lost Female Inventor], September 1, 2018, National Women’s History Museum, #link("https://openstax.org/r/womens_history")[#emph[“Monopoly’s] Lost Female Inventor,”]
]


  
  
    
=== Identifying and Naming Isomorphisms


    When two graphs are isomorphic, meaning they have the same structure, there is a correspondence between their vertices, which can be named by listing corresponding pairs of vertices. This list of corresponding pairs of vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph is called an #strong[isomorphism]. Consider the isomorphic graphs in . In , we could replace the labels Graph #emph[F] with the labels from Graph #emph[A] and have an identical graph, as in .


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.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((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph F])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[g])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[i])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[j])
})]
)]),
  alt: "Two graphs are labeled graph A and graph F. Graph A has four vertices: b, c, d, and e. The edges connect b c, c e, e d, d b, and d c. Graph F has four vertices: g, h, i, and j. The edges connect g h, h j, j i, I g, and I h.", caption: [Identical Graphs with Different Labels],
)


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph A])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.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((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph F])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.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((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
})]
)]),
  alt: "Two graphs are labeled graph A and graph F. Graph A has four vertices: b, c, d, and e. The edges connect b c, c e, e d, d b, and d c. Graph F has four vertices: b, c, d, and e. The edges connect b c, c e, e d, d b, and d c. The vertices, g, h, i, and j are struck through and written as b, c, d, and e.", caption: [Corresponding Vertices],
)


    So, we can identify an isomorphism between Graph #emph[A] and Graph #emph[F] by listing the corresponding pairs of vertices: #emph[b-g], #emph[c-h], #emph[d-i], and #emph[e-j]. Notice that #emph[b] is adjacent to #emph[c] and #emph[g] is adjacent to #emph[h]. This must be the case since #emph[b] corresponds to #emph[g] and #emph[c] corresponds to #emph[h]. The same is true for other pairs of adjacent vertices.


    An isomorphism between graphs is not necessarily unique. There can be more than one isomorphism between two graphs. We can see how to form a different isomorphism between Graph #emph[A] and Graph #emph[F] from  by rotating Graph #emph[F] clockwise and comparing the rotated version of #emph[F] to Graph #emph[A] as in YOUR TURN 12.13. Now, we can see that a second isomorphism exists, which has the correspondence: #emph[b-j], #emph[d-h], #emph[c-i], and #emph[e-g] as shown.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph F])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[g])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[h])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[i])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph A])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[b])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.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((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[e])
})]
)]),
  alt: "Graph F is converted into graph A. Graph F has four vertices: g, h, i, and j. The edges connect g h, h j, j i, i g, and i h. Graph F is rotated 90 degrees clockwise. Graph F is rotated 180 degrees clockwise to obtain graph A. Graph A has four vertices: b, c, d, and e. The edges connect b c, c e, e d, d b, and d c.", caption: [Transforming Graph #emph[F] into Graph #emph[A]],
)


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[When you name isomorphisms, one way to check that your answer is reasonable is to make sure that the degrees of corresponding vertices are equal.]
]


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Determine_If_Two")[Determine If Two Graphs Are Isomorphic and Identify the Isomorphism]
]


    #examplebox("Example 3")[Identifying Isomorphisms][
In Example 1, we showed that the Graphs #emph[B]#sub[1] and #emph[B]#sub[2] in  are isomorphic. In , labels have been assigned to the vertices of Graphs #emph[B]#sub[1] and #emph[B]#sub[2]. Identify an isomorphism between them by listing corresponding pairs of vertices.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[B 1])
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[B 2])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[p])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[q])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[r])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[s])
})]
)]),
  alt: "Two graphs are labeled graph B 1 and graph B 2. Graph B 1 has four vertices: a, b, c, and d. The edges connect a c, b c, a d, and c d. Graph B 2 has four vertices: p, q, r, and s. The edges connect p q, q r, r s, and r p.", caption: [Two Isomorphic Graphs],
)


      
      #solutionbox[
showed how to transform Graph #emph[B]#sub[1] to get Graph #emph[B]#sub[2]. In , we will do the same, but this time we will include the labels.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph B 1])
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph B 2])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[p])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[q])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[r])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[s])
})]
)]),
  alt: "Graph B 1 is converted into graph B 2. Graph B 1 has four vertices: a, b, c, and d. The edges connect a c, b c, a d, and c d. Graph B 1 is rotated 90 degrees counterclockwise. Graph B 1 is again rotated 180 degrees clockwise to obtain graph B 2. Graph B 2 has four vertices: p, q, r, and s. The edges connect p q, q r, r s, and r p.", caption: [Transform Graph #emph[B]#sub[1] into Graph #emph[B]#sub[2]],
)


        From YOUR TURN 12.13, we can see the corresponding vertices: #emph[a-q], #emph[d-p], #emph[c-r], and #emph[b-s], which is an isomorphism of the two graphs.
]
]


    
    #examplebox("Example 4")[Recognizing an Isomorphism][
Determine whether Graphs #emph[G] and #emph[S] in  are isomorphic. If not, explain how they are different. If so, name the isomorphism.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph G])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph S])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[n])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[m])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[o])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[q])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[r])
})]
)]),
  alt: "Two graphs are labeled graph G and graph S. Graph G has six vertices: a, b, c, d, e, and f. The edges connect a b, b c, c d, d e, f b, and f d. Graph S has six vertices: n, m, o, p, q, and r. The edges connect n m, m o, o p, p q, r m, a d r o.", caption: [Graph #emph[G] and Graph #emph[S]],
)


      
      #solutionbox[
#strong[Step 1:] Check for any differences.


        - Vertices: Graphs #emph[G] and #emph[S] each have six vertices.
- Edges: Graphs #emph[G] and #emph[S] each have six edges.
- Degrees: Each graph also has two vertices of degree 1, two vertices of degree 2, and two vertices of degree 3.
- Cycles: From , we can see that Graph #emph[G] contains a quadrilateral cycle (#emph[b], #emph[f], #emph[d], #emph[c]) but Graph #emph[S] has no quadrilaterals. Also, Graph #emph[S] contains a triangle cycle (#emph[m], #emph[r], #emph[o]) but Graph #emph[G] has no triangles. This means that the graphs are not isomorphic.


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph G])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, 21.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph S])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: (paint: rgb("#D62128"), 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: (paint: rgb("#D62128"), thickness: 1.4pt))
  line((-36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.4pt))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[n])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[m])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[o])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[p])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[q])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[r])
})]
)]),
  alt: "Two graphs are labeled graph G and graph S. Graph G has six vertices: a, b, c, d, e, and f. The edges connect a b, b c, c d, d e, f b, and f d. The edges, f b, b c, c d, and f d are highlighted. Graph S has six vertices: n, m, o, p, q, and r. The edges connect n m, m o, o p, p q, r m, a d r o. The edges, r m, m o, and r o are highlighted.", caption: [Comparing Subgraphs],
)


        #strong[Step 2:] This step is not necessary because we now know Graphs #emph[G] and #emph[S] are not isomorphic.
]
]


    
  
  
    
=== Complementary Graphs


    Suppose that you are a camp counselor at Camp Woebegone and you are holding a camp Olympics with four events. The campers have signed up for the events. You drew a graph in  to help you visualize which events have campers in common.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})]),
  alt: "A graph with four vertices. The vertices are labeled, a, b, c, and d. The edges connect a b, b d, d c, and c a.", caption: [Graph of Events with Campers in Common],
)


    Graph #emph[E] in  shows that some of the same campers will be in events #emph[a] and #emph[b], as well as #emph[b] and #emph[d], #emph[c] and #emph[d], and #emph[a] and #emph[c]. What do you think the graph would look like that represented the events that do not have campers in common? It would have the same vertices, but any pair of adjacent edges in Graph #emph[E], would not be adjacent in the new graph, and vice versa. This is called a #strong[complementary] graph, as shown. Two graphs are complementary if they have the same set of vertices, but any vertices that are adjacent in one, are not adjacent in the other. In this case, we can say that one graph is the #strong[complement]of the other.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph E])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[complement of E])
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})]
)]),
  alt: "Two graphs: graph E and complement of E. Graph E has four vertices: a, b, c, and d. The edges connect a b, b d, d c, and c a. The complement of E has four vertices: a, b, c, and d. The edges connect a d, and b c.", caption: [Graphs of Camp Olympics],
)


    One way to find the complement of a graph is to draw the complete graph with the same number of vertices and remove all the edges that were in the original graph. Let’s say you wanted to find the complement of Graph #emph[E] from , and you didn’t already know it was Graph #emph[F]. You could start with the complete graph with four vertices and remove the edges that are in Graph #emph[E] as shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (0.00pt, 42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})]
)]),
  alt: "Three graphs. The first graph has four vertices: a, b, c, and d. The edges connect a b, b d, d c, c a, a d, and b c. The second graph has four vertices: a, b, c, and d. The edges connecting a b, b d, d c, and c a are struck through. The edges connect a d and c b. The third graph has four vertices: a, b, c, and d. The edges connect a d and c b.", caption: [Use Complete Graph to Find Complement],
)


    #examplebox("Example 5")[Finding a Complement][
A particular high school has end-of-course exams in (E3) English 3, (E4) English 4, (M) Advanced Math, (C) Calculus, (W) World History, (U) U.S. History, (B) Biology, and (P) Physics. No English 3 students are taking English 4, World History, or Biology; no English 4 students are also in Calculus, Advanced Math, U.S. History, or Physics; no Physics students are also taking Advanced Math; No World History students are also taking U.S. History; and no Advanced Math students are also taking Calculus.


        + Create a graph in which the vertices represent the exams, and an edge between a pair of vertices indicates that there are no students taking both exams.
+ Find the complement of the graph in part 1.
+ Explain what the graph in part 2 represents.


      
      #solutionbox[
+ In , we have drawn a vertex for each exam and edges between any vertices that have no students in common.
     #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-29.70pt, 29.70pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, 29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((-29.70pt, 29.70pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[U])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[W])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[C])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[M])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[E4])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[E3])
})]),
  alt: "A graph has eight vertices. The vertices are labeled P, B, U, W, C, M, E 4, and E 3. The edges connect E 3 B, E 3 E 4, E 4 M, M C, E 4 C, E 4 P, E 3 U, E 3 W, E 4 U, and U W.", caption: [Graph of Exams with No Students in Common],
)
+ One way to get the complement of the graph in  is to draw a complete graph with the same number of vertices and remove the edges they have in common as shown.
     #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[U])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[W])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[C])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[M])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[E4])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[E3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-29.70pt, -29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (-29.70pt, 29.70pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[U])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[W])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[C])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[M])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[E4])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[E3])
})]
)]),
  alt: "Two graphs. Each graph has eight vertices: P, B, U, W, C, M, E 4, and E 3. In the first graph, all vertices are interconnected. The second graph is the same as the first. The edges connecting E 3 E 4, E 4 M, M C, E 4 C, E 3 B, E 4 U, U W, E 3 W, and P M are struck through.", caption: [Remove Unwanted Edges from Complete Graph],
)

The final graph of the complement is in .

#figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, 29.70pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-29.70pt, -29.70pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-29.70pt, -29.70pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (-29.70pt, 29.70pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, 29.70pt), text(size: 9pt, fill: black)[B])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[U])
  circle((29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((29.70pt, -29.70pt), text(size: 9pt, fill: black)[W])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[C])
  circle((-29.70pt, -29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, -29.70pt), text(size: 9pt, fill: black)[M])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[E4])
  circle((-29.70pt, 29.70pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-29.70pt, 29.70pt), text(size: 9pt, fill: black)[E3])
})]),
  alt: "A graph. The graph has eight vertices: P, B, U, W, C, M, E 4, and E 3. All vertices are interconnected.", caption: [Graph of Exams with Students in Common],
)
+ In the graph in , the vertices are still the exams, and a pair of adjacent vertices represents a pair of exams that have students in common.
]
]


    
    When two graphs are really the same graph, they have the same missing edges. So, when two graphs have a lot of edges, it may actually be easier to determine if they are isomorphic by looking at which edges are missing rather than which edges are included. In other words, we can determine if two graphs are isomorphic by checking if their complements are isomorphic.


    #examplebox("Example 6")[Using a Complement to Find an Isomorphism][
Use  to answer each question.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Graph K])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  bezier((24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-5.16pt, -7.10pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  bezier((24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-10.10pt, -13.90pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[L])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[M])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[O])
})]),
  alt: "Graph K has five vertices: P, L, M, N, and O. The edges connect P L, L M, M N, M O, L O, M P, and M O.", caption: [Graph #emph[K]],
)


        + Find the complement of Graph #emph[K].
+ Identify an isomorphism between the complement of Graph #emph[K] from part 1, and the complement of Graph #emph[H] in YOUR TURN 12.17.
+ Confirm that the correspondence between the vertices you found in part 2 also gives an isomorphism between Graph #emph[H] from YOUR TURN 12.17, and Graph #emph[K] from .


      
      #solutionbox[
+ The complement of Graph #emph[K] can be found by removing the edges of Graph #emph[K] from a complete graph with the same vertices as shown.
     #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  bezier((24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-5.16pt, -7.10pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  bezier((24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-10.10pt, -13.90pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[P])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[L])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[M])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[O])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (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)[P])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[L])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[M])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[O])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[L])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[M])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[O])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[P])
})]
)]),
  alt: "Three graphs. The first graph has five vertices: P, L, M, N, and O. The edges connect P L, L M, M N, M O, L O, M P, and M O. The second graph is the same as that of the first graph. The edges connecting L M, M N, M O, L O, L P, and M P are struck through. The third graph has five vertices: L, M, N, O, and P. The edges connect L N, N O, and O P.", caption: [Find Complement of Graph #emph[K]],
)
+ An isomorphism between the complement of Graph #emph[K] and the complement of Graph #emph[H] is #emph[A-M], #emph[C-L], #emph[E-N], #emph[B-O], and #emph[D-P], which is confirmed by transforming the complement of Graph #emph[K] in .
     #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[A])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[B])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[C])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[D])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[E])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  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((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[B])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[C])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[D])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[E])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  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((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[B])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[C])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[D])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[E])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[L])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[M])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[O])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[P])
})]
)]),
  alt: "Four graphs. The first three graphs have the vertices, A, B, C, D, and E. The edges of the first graph connect E B, B D, and E C. The edge E C is moved clockwise to the left. The edge, B D is moved counterclockwise to the right. The edges of the second graph connect E C, E, and B D. The edges of the third graph connect C E, E B, and B D. The edges are rotated such that the edge, D B lies at the bottom. The fourth graph has five vertices: L, M, N, O, and P. The edges connect L N, N O, and O P.", caption: [Isomorphism between Complements of #emph[K] and #emph[H]],
)
+ shows how Graph #emph[K] can be transformed into Graph #emph[H] to confirm that the correspondence is #emph[A-M], #emph[C-L], #emph[E-N], #emph[B-O], and #emph[D-P] also gives an isomorphism between Graph #emph[K] and Graph #emph[H].
     #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[L])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[M])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[O])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[P])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[L])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[M])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[O])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[P])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[L])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[M])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[N])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[O])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[P])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[H])
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[A])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[B])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[C])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[D])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[E])
})]
)]),
  alt: "Four graphs. The first three graphs have the vertices, L, M, N, O, and P. The edges in each graph connect P L, P M, P N, L O, L M, M N, and M O. In the second graph, the edges, P L, L O, and L M are moved. In the third graph, the edge, M N is moved to the left. The fourth graph, H has five vertices: A, B, C, D, and E. The edges connect A E, A D, A C, A B, B C, C D, and D E.", caption: [Isomorphism between #emph[K] and #emph[H]],
)


        This means we now have three conditions that guarantee two graphs are isomorphic.


        #strong[First Way:] One graph can be transformed into the other without breaking existing connections or adding new ones.


        #strong[Second Way:] There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.


        #strong[Third Way:] Their complements are isomorphic.


        If any one of these statements is true, then they are all true. If any one of these statements is false, then they are all false.
]
]


    
    #notebox("Work It Out", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
Here is an activity you can do with a few of your classmates that will build your graph comparison skills.


      #strong[Step 1:] Draw a planar graph with the following characteristics: exactly five vertices, one vertex of degree four, at least two vertices of degree three, and exactly eight edges. Give names to the vertices. Make sure you do not use the same letters or numbers to label your vertices as your classmates do.


      #strong[Step 2:] Analyze your graph. What is the degree of each vertex? Does your graph have any cyclic subgraphs? If so, list them and indicate their sizes.


      #strong[Step 3:] Draw and analyze the complement of your graph. How many edges and vertices does it have? What is the degree of each vertex? Does the complementary graph have any cyclic subgraphs? If so, list them and indicate their sizes.


      #strong[Step 4:] Compare your graphs to each of your classmates’ graphs. Does your graph have the same number of edges and vertices as the graph of your classmate? Does your graph have the same size cyclic subgraphs as the graph of your classmate? How does the complement of your graph compare to the complement of the graph of your classmate? Determine if your graph is isomorphic to your classmates’ graph. If so, give a correspondence that demonstrates the isomorphism. If not, explain how you know.
]


  
  
  
  
    
=== Key Terms


    - isomorphic
- isomorphism
- planar
- nonplanar
- complement
- complementary


  
  
    
=== Key Concepts


    - Two graphs are isomorphic if they have the same structure.
- When graphs are relatively small, we can use visual inspection to identify an isomorphism by transforming one graph into another without breaking connections or adding new ones.
- An isomorphism between two graphs preserves adjacency.
- If two graphs differ in number of vertices, number of edges, degrees of vertices, or types of subgraphs, they cannot be isomorphic.
- When the complements of two graphs are isomorphic, so are the graphs themselves.


  
  
    
=== Videos


    - #link("https://openstax.org/r/Determine_If_Two")[Determine If Two Graphs Are Isomorphic and Identify the Isomorphism]