#set document(title: "12.2 Graph Structures", 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.2#h(0.6em)Graph Structures


  #figure(figph[An M R I image shows the active nodes in the brain.], alt: "An M R I image shows the active nodes in the brain.", caption: [Neuroimaging shows brain activity.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Describe and interpret relationships in graphs.
+ Model relationships with graphs.


    Graph theory is used in neuroscience to study how different parts of the brain connect. Neurobiologists use functional magnetic resonance imaging (fMRI) to measure levels of blood in different parts of the brain, called nodes. When nodes are active at the same time, it suggests there is a functional connection between them so they form a network. This network can be represented as a graph where the vertices are the nodes and the functional connections are the edges between them. (Mikey Taylor, "Graph Theory & Machine Learning in Neuroscience," Medium.com, June 24, 2020.


  
  
    
=== Importance of the Degrees of Vertices


    One reason scientists study these networks is to determine how successful the communication within a network continues to be when it experiences failures in nodes and connections. Graphs can be used to study the resilience of these networks. (Mikey Taylor, "Graph Theory & Machine Learning in Neuroscience," Medium.com, June 24, 2020)


    #examplebox("Example 1")[Using Graphs to Understand Relationships][
The graphs in  represent neural networks, where the vertices are the nodes, and the edges represent functional connections between them. Which graph do you think would represent a network with the highest resistance to failure? Which graph would probably be the most vulnerable to failure? How might this relate to the degrees of the vertices?


        #figure(figph[Three graphs, graph A, graph B, and graph C represent models of neural networks. The graphs have n number of edges and vertices.], alt: "Three graphs, graph A, graph B, and graph C represent models of neural networks. The graphs have n number of edges and vertices.", caption: [Models of Neural Networks])


      
      #solutionbox[
Graph #emph[B] represents a network that would have the highest resistance to failure because there are more edges connecting the nodes indicating there are more connections between nodes than on either of the other graphs. This would make the network more resistant to failure because there are more options to work around a faulty edge or node. Graph #emph[A] would probably be the most susceptible to failure because the network depends on a few particular edges and vertices for connections. There are more vertices of higher degree in Graph #emph[B] than in Graph #emph[A] because there are more edges connecting the nodes.
]
]


    
  
  
    
=== Relating the Number of Edges to the Degrees of Vertices


    In the applications of graph theory to neuroscience and sociology in  and YOUR TURN 12.6, there was a correlation between the degrees of vertices and the resilience of a network. Researchers in many fields have also observed a direct relationship between the number of edges in a graph and the degrees of the vertices. To begin to understand this relationship, consider a graph with five vertices and zero edges as in .


    #figure(figph[A graph has five vertices and no edges. The vertices are labeled 0.], alt: "A graph has five vertices and no edges. The vertices are labeled 0.", caption: [Graph with Five Vertices and zero Edges])


    Instead of being marked with a name, each vertex in  is marked with its degree. In this case, all of the degrees are 0 so the sum of the degrees is also zero. Suppose that we add an edge between any two existing vertices and indicate the degrees of the vertices. This gives us a graph with five vertices and one edge like the graph in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  circle((-39.94pt, 25.98pt), 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)[0])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[0])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[0])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[1])
})]),
  alt: "A graph has five vertices: three vertices are labeled 0 and two others are labeled 1. The vertices labeled 1 are connected with an edge.", caption: [Graph with Five Vertices and One Edge],
)


    Note that the degrees of two vertices increased, each by 1. So, the sum of the degrees is now 2. Suppose that we continue in this way, adding one edge at a time and making note of the number of edges and the sum of the degrees of the vertices as 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)[edges: 2. Sum of degrees: 4.])
  bezier((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-28.32pt, -9.20pt), stroke: 0.7pt + black)
  bezier((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-36.31pt, -11.80pt), 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)[0])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[0])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[2])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[edges: 3. Sum of degrees: 6.])
  circle((-24.69pt, -20.98pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-28.32pt, -9.20pt), stroke: 0.7pt + black)
  bezier((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-36.31pt, -11.80pt), 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((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[1])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[2])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[edges: 4. Sum of degrees: 8.])
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  bezier((24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-5.16pt, -7.10pt), 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)[1])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[1])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[1])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[2])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[3])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[edges: 5. Sum of degrees: 10.])
  bezier((39.94pt, 12.98pt), (-24.69pt, -33.98pt), (5.16pt, -7.10pt), stroke: 0.7pt + black)
  circle((-24.69pt, -20.98pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((-39.94pt, 12.98pt), (-24.69pt, -33.98pt), (-36.31pt, -11.80pt), stroke: 0.7pt + black)
  bezier((39.94pt, 12.98pt), (-24.69pt, -33.98pt), (10.10pt, -13.90pt), stroke: 0.7pt + black)
  bezier((-24.69pt, -33.98pt), (-39.94pt, 12.98pt), (-36.31pt, -11.80pt), 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((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[1])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[3])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[3])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[2])
})]
)]),
  alt: "Four graphs. The first graph is labeled edges: 2. Sum of degrees: 4. The graph has five vertices: two vertices labeled 0, two labeled 1, and one labeled 2. The edges connect 1 2 and 1 2. The second graph is labeled edges: 3. Sum of degrees: 6. The graph has five vertices: four vertices labeled 1 and one labeled 2. The edges connect 1 1, 1 2, and 1 2. The third graph is labeled edges: 4. Sum of degrees: 8. The graph has five vertices: three vertices labeled 1, one labeled 2, and one labeled 3. The edges connect 1 2, 2 3, 1 3, and 1 3. The fourth graph is labeled edges: 5. Sum of degrees: 10. The graph has five vertices: two vertices labeled 1, two labeled 3, and one labeled 2. The edges connect 1 3, 3 3, 2 3, 1 3, and 3 2.", caption: [Comparing Number of Edges to Sum of Degrees],
)


    demonstrates a characteristic that is true of all graphs of any shape or size. When the number of edges is increased by one, the sum of the degrees increases by two. This happens because each edge has two ends and each end increases the degree of one vertex by one unit. As a result, the sum of the degrees of the vertices on any graph is always twice the number of edges. This relationship is known as the #strong[Sum of Degrees Theorem].


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
For the Sum of Degrees Theorem,


      #math.equation(block: true, alt: "sum of the degrees equals 2 times number of edges")[$"sum of the degrees" = 2 × "number of edges"$]
      or


      #math.equation(block: true, alt: "number of edges equals the fraction sum of degrees over 2")[$"number of edges" = frac("sum of degrees", 2)$]
]


    #examplebox("Example 2")[Finding the Sum of Degrees][
Suppose that a graph has five edges.


        + Find the sum of the degrees of the vertices.
+ Draw two different graphs that demonstrate this conclusion.


      
      #solutionbox[
+ The sum of the degrees is twice the number of edges: 2 × 5=10. The sum of the degrees is 10.
+


        #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph 1])
  bezier((-36.37pt, 21.00pt), (-36.37pt, -21.00pt), (-40.57pt, -0.00pt), stroke: 0.7pt + black)
  circle((-36.37pt, -8.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((-36.37pt, -8.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  circle((-36.37pt, -8.00pt), radius: 8pt, stroke: 0.7pt + black, fill: none)
  bezier((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), (-40.57pt, -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((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[2])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.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)[2])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[2])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[1])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph 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((0.00pt, -29.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)[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)[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)[2])
})]
)]),
  alt: "Two graphs are labeled graph 1 and graph 2. Graph 1 has six vertices labeled 1, 2, 2, 2, 2, and 1. The edges connect 1 2, 2 2, 2 2, 2 2, and 2 1. Graph 2 has four vertices labeled 3, 2, 3, and 2. The edges connect 3 2, 2 3, 3 2, 2 3, and 3 3.", caption: none,
)
]
]


    
  
  
    
=== Completeness


    Suppose that there were five strangers in a room, #emph[A], #emph[B], #emph[C], #emph[D], and #emph[E], and each one would be introduced to each of the others. How many introductions are necessary? One way to begin to answer this question is to draw a graph with each vertex representing an individual in the room and each edge representing an introduction as 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)[4 edges])
  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)
  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: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[3 more edges])
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  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((-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: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[2 more edges])
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  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((-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)
  line((-24.69pt, -33.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  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: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[1 more edge])
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  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((-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)
  line((-24.69pt, -33.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-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: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[4 plus 3 plus 2 plus 1 equals 10 edges])
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  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((-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)
  line((-24.69pt, -33.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-39.94pt, 12.98pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((-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])
})]
)]),
  alt: "Five graphs titled 4 edges, 3 more edges, 2 more edges, 1 more edge, and 4 plus 3 plus 2 plus 1 equals 10 edges. The first graph shows the edges connecting the following vertices: A E, A D, A C, and A B. The second graph shows the edges connecting the following vertices: A E, A B, A D, A C, E B, B C, and B D. The third graph shows the edges connecting the following vertices: A E, A B, A D, A C, E B, B C, B D, D C, and E C. The fourth graph shows the edges connecting the following vertices: A E, A B, A D, A C, E B, B C, B D, D C, E C, and E D. The fifth graph shows the edges connecting the following vertices: A E, A B, A D, A C, E B, B C, B D, D C, E C, and E D.", caption: [Model of Introductions between Five Strangers],
)


    Let’s approach the problem by thinking about how many new people Person #emph[A] would meet, then Person #emph[B], and so on, making sure not to repeat any introductions. The first graph in  shows Person #emph[A] meeting Persons #emph[B], #emph[C], #emph[D], and #emph[E], for a total of 4 introductions. The next graph shows that Person #emph[B] still has to meet Persons #emph[C], #emph[D], and #emph[E], for a total of 3 more introductions. The next graph shows that Person #emph[C] still has to meet Persons #emph[D] and #emph[E], which is 2 more introductions. The next graph shows that Person #emph[D] only remains to meet Person #emph[E], which is 1 more introduction. The final graph has #math.equation(block: false, alt: "4 plus 3 plus 2 plus 1 equals 10")[$4 + 3 + 2 + 1 = 10$] edges representing 10 introductions. The last graph is an example of a #strong[complete] graph because each pair of vertices is joined by an edge. Another way of saying this is that the graph is complete because each vertex is adjacent to every other vertex. shows complete graphs with three, four, five, and six vertices.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[b])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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), (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)
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), 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((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-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])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})]
)]),
  alt: "Four graphs. The first graph shows three vertices, a, b, and c. The edges connect a c, a b, and c b. The second graph shows four vertices, a, b, c, and d. The edges connect a b, b c, c d, a d, a c, and b d. The third graph shows five vertices, a, b, c, d, and e. The edges connect a b, b c, c d, d e, e a, a d, a c, b e, b d, and c e. The fourth graph shows six vertices, a, b, c, d, e, and f. All the vertices are interconnected using 15 edges.", caption: [Complete Graphs with Up to Six Vertices],
)


    Suppose we want to know the number of introductions necessary in a room with six people. This would be represented by a complete graph with six vertices, and the total number of introductions would be #math.equation(block: false, alt: "5 plus 4 plus 3 plus 2 plus 1 equals 15")[$5 + 4 + 3 + 2 + 1 = 15$], the number of edges in the graph. In fact, you can always find the number of introductions in a room with #math.equation(block: false, alt: "n")[$n$] people by adding all the whole numbers from 1 to #math.equation(block: false, alt: "n minus 1")[$n − 1$].


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
The number of edges in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is the sum of the whole numbers from 1 to #math.equation(block: false, alt: "n minus 1")[$n − 1$], #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus open parenthesis n minus 1 close parenthesis")[$1 + 2 + 3 + ⋯ + ( n − 1 )$].
]


    Suppose that we want to determine how many introductions are necessary in a room with 500 strangers. In other words, suppose that we want to determine the number of edges in a complete graph with 500 vertices. Adding up all the numbers from 1 to 499 could take a long time! In the next example, we use the Sum of Degrees Theorem to make the problem more manageable.


    #examplebox("Example 3")[Using the Sum of Degrees Theorem][
Use the Sum of Degrees Theorem to determine the number of introductions required in a room with


        + 6 strangers.
+ 10 strangers.
+ #math.equation(block: false, alt: "n")[$n$] strangers.


      
      #solutionbox[
+ Since there are 6 strangers, there are 6 vertices. Since each individual must meet 5 other individuals, there are 5 edges meeting at each vertex which means each vertex has degree 5. Since there are 6 vertices of degree 5, the sum of degrees is #math.equation(block: false, alt: "6 times 5 equals 30")[$6 ⋅ 5 = 30$]. By the Sum of Degrees Theorem, the number of edges is half the sum of the degrees, which is #math.equation(block: false, alt: "the fraction 30 over 2 equals 15")[$display(frac(30, 2)) = 15$]. So, the total number of introductions is 15.
+ Since there are 10 strangers, there are 10 vertices. Since each individual must meet 9 other individuals, there are 9 edges meeting at each vertex which means each vertex has degree 9. Since there are 10 vertices of degree 9, the sum of degrees is #math.equation(block: false, alt: "10 times 9 equals 90")[$10 ⋅ 9 = 90$]. By the Sum of Degrees Theorem, the number of edges is half the sum of the degrees, which is #math.equation(block: false, alt: "the fraction 90 over 2 equals 45")[$display(frac(90, 2)) = 45$]. So, the total number of introductions is 45.
+ Since there are #math.equation(block: false, alt: "n")[$n$] strangers, there are #math.equation(block: false, alt: "n")[$n$] vertices. Since each individual must meet #math.equation(block: false, alt: "n minus 1")[$n − 1$] other individuals, there are #math.equation(block: false, alt: "n minus 1")[$n − 1$] edges meeting at each vertex which means each vertex has degree #math.equation(block: false, alt: "n minus 1")[$n − 1$]. Since there are #math.equation(block: false, alt: "n")[$n$] vertices of degree #math.equation(block: false, alt: "n minus 1")[$n − 1$], the sum of degrees is #math.equation(block: false, alt: "n open parenthesis n minus 1 close parenthesis")[$n ( n − 1 )$]. By the Sum of Degrees Theorem, the number of edges is half the sum of the degrees, which is #math.equation(block: false, alt: "the fraction n open parenthesis n minus 1 close parenthesis over 2")[$frac(n ( n − 1 ), 2)$]. So, the total number of introductions is #math.equation(block: false, alt: "the fraction n open parenthesis n minus 1 close parenthesis over 2")[$frac(n ( n − 1 ), 2)$].
]
]


    
    Now we have a shorter way to calculate the number of introductions in a room with #math.equation(block: false, alt: "n")[$n$] strangers, and the number of edges on a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices. Let’s update our formula.


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
The number of edges in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus open parenthesis n minus 1 close parenthesis equals the fraction n open parenthesis n minus 1 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + ( n − 1 ) = frac(n ( n − 1 ), 2)$].
]


  
  
    
=== Subgraphs


    Sometimes a graph is a part of a larger graph. For example, the graph of South Florida Airports from  is part of a larger graph that includes Orlando International Airport in Central Florida, which is shown in


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[TPA])
  circle((36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[KYW])
  circle((36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[MIA])
  circle((0.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[FLL])
  circle((-36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[PBI])
  circle((-36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[MCO])
})]),
  alt: "A graph with six vertices. The edges connect Tampa T P A with Key West E Y W, Miami M I A, Fort Lauderdale F L L, and West Palm Beach P B I. An edge connects Key West with Miami. An edge connects Key West with Fort Lauderdale. Edges from Orlando M C O connect with Key West, Miami, and Fort Lauderdale.", caption: [Orlando and South Florida Airports],
)


    The graph in  includes an additional vertex, MCO, and additional edges shown with dashed lines. The graph of direct flights between South Florida airports from  is called a #strong[subgraph] of the graph that also includes direct flights between Orlando and the same South Florida airports in . In general terms, if Graph #emph[B] consists entirely of a set of edges and vertices from a larger Graph #emph[A], then #emph[B] is called a subgraph of #emph[A].


    #examplebox("Example 4")[Identifying a Subgraph][
In , Graph #emph[G] is given, along with four diagrams. Determine whether each diagram is or is not a subgraph of Graph #emph[G] and explain why.


        #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 G])
  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)
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.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])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Diagram J])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  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((-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)
  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: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Diagram K])
  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((-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)[e])
  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)[Diagram L])
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (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)[Diagram M])
  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((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)
  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)[f])
})]
)]),
  alt: "Five graphs. Graph G has five vertices: a, b, c, d, and e. The edges connect a b, b c, c d, d e, e a, a d, and b e. Diagram J has five vertices: a, b, c, d, and e. The edges connect a b, a e, a d, e c, and c d. Diagram K has four vertices: a, e, c, and d. The edges connect a e, a d, and d c. Diagram L has four vertices: a, b, c, and d. The edges connect a d, d c, and b c. Diagram M has five vertices: a, b, c, d, and f. The edges connect a b, b c, c d, a f, and f d.", caption: [Graph #emph[G] and Potential Subgraphs],
)


      
      #solutionbox[
- Diagram #emph[J] is not a subgraph of Graph #emph[G] because edge #emph[ec] is not in Graph #emph[G].
- Diagram #emph[K] is a subgraph of Graph #emph[G] because all of its vertices and edges were part of Graph #emph[G].
- Diagram #emph[L] is not a graph at all, because there is a line extending from vertex #emph[a] that does not connect #emph[a] to another vertex. So, Diagram #emph[L] cannot be a subgraph.
- Diagram #emph[M] is not a subgraph of Graph #emph[G] because it contains a vertex #emph[f], which is not part of #emph[G].
]
]


    
  
  
    
=== Identifying and Naming Cycles


    #figure(figph[An illustration represents the water cycle. Through the evaporation process, water from the ocean gets evaporated. The evaporated water converts into clouds through the condensation process. Through the precipitation process, rain pours down from clouds. The surface runoff water from the mountains reaches the lake and from the lake to the ocean.], alt: "An illustration represents the water cycle. Through the evaporation process, water from the ocean gets evaporated. The evaporated water converts into clouds through the condensation process. Through the precipitation process, rain pours down from clouds. The surface runoff water from the mountains reaches the lake and from the lake to the ocean.", caption: [The water cycle begins and ends with water.])


    When you think of a cycle in everyday life, you probably think of something that begins and ends the same way. For example, the water cycle  begins with water in a lake or ocean, which evaporates into water vapor, condenses into clouds, and then returns to earth as rain or some other form of precipitation that settles into lakes or oceans. A #strong[cycle] in graph theory is similar in that it begins and ends in the same way: It is a series of connected edges that begin and end at the same vertex but otherwise never repeat any vertices.


    In a cycle, there are always the same number of vertices as edges, and all vertices must be of degree 2. Cycles are often referred to by the number of vertices. For example, a cycle with 5 vertices can be called a 5-cycle. Cycles can also be named after polygons based on the number of edges. For example a 5-cycle is also called a pentagon.  lists these names for cycles of size 3 through size 10.


    #figure(table(
  columns: 3, align: left, inset: 6pt,
  table.header([Cycle Category], [Number of Edges], [Example]),
  [triangle], [3], [],
  [quadrilateral], [4], [],
  [pentagon], [5], [],
  [hexagon], [6], [],
  [heptagon], [7], [],
  [octagon], [8], [],
  [nonagon], [9], [],
  [decagon], [10], [],
))


    There are many more polygon names, including a megagon that has a million edges and a googolgon that has #math.equation(block: false, alt: "10 to the power 100")[$10^(100)$] edges, but usually we just say #math.equation(block: false, alt: "n")[$n$]-gon when the number #math.equation(block: false, alt: "n")[$n$] is past 10. For example, a cycle with 11 edges could be called an 11-gon.


    Notice that the 10-cycle, or decagon, appears to cross over itself in . Remember, graphs can be drawn differently but represent the same connections. In , the same decagon is transformed into a graph that does not appear to overlap itself. We have done this without changing any of the connections so both diagrams represent the same relationships, and both diagrams are considered decagons.


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 66.43pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Decagon])
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((0.00pt, -45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, -14.04pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((-26.71pt, 36.76pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[1])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[2])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[3])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[4])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[5])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[6])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[7])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[8])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[9])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[10])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 45.43pt), (26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((0.00pt, -45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (-43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, -14.04pt), (-43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  line((-26.71pt, 36.76pt), (0.00pt, 45.43pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[1])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[2])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[3])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[4])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[5])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[6])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[7])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[8])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[9])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[10])
})]
)]),
  alt: "Two graphs. The first graph represents a decagon with 10 edges and 10 vertices. The second graph shows 10 edges and 10 vertices. The edges do not overlap.", caption: [Transformation of a Decagon],
)


    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Googol to Google]


      Did the name "googolgon" ring a bell for you? If so, there is a good reason for it. The creators of Google.com renamed their search engine Google, a misspelled reference to the number "googol" alluding to the enormous number of calculations their algorithm can tackle. A googol is a 1 followed by 100 zeroes, or #math.equation(block: false, alt: "10 to the power 100")[$10^(100)$]. (William L. Hosch, "Google, American Company," https://www.britannica.com/topic/Google-Inc, Encyclopedia Britannica online)
]


  
  
    
=== Cyclic Subgraphs and Cliques


    When cycles appear as subgraphs within a larger graph, they are called #strong[cyclic subgraphs]. Cyclic subgraphs are named by listing their vertices sequentially. The vertex where you begin is not important. Graph #emph[K] in  has two triangle cycles (#emph[g], #emph[h], #emph[j]) and (#emph[h], #emph[i], #emph[j]), and one quadrilateral cycle (#emph[g], #emph[h], #emph[i], #emph[j]).


    #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 K])
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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: *
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  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((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[h])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[h])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[i])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[j])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  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: "Four graphs. Graph K shows four vertices: g, h, i, and j. The edges connect h i, i j, j g, g h, and h j. The second graph shows (g, h, j). The edges connect g h, g j, and j h. The third graph shows (h, i, j). The edges connect h i, i j, and j h. The fourth graph shows (g, h, i, j). The edges connect g h, h i, i j, and j g.", caption: [Cycles in Graph #emph[K]],
)


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[The same cycle can be named in many ways, but we must keep in mind that listing two vertices consecutively indicates an edge exists between them. For example, (g, h, i, j) can also be named (h, i, j, g) or (j, i, h, g). However, you cannot name it (g, i, h, j,) which doesn't reflect the correct order of the vertices. We can see that the order (g, i, h, j) is incorrect because the cycle has no edges gi or hj.]
]


    #examplebox("Example 5")[Identifying Cyclic Subgraphs][
Identify the types of cyclic subgraphs in Graph #emph[H] in  and name them.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((40.95pt, -9.35pt), (18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((18.22pt, -37.84pt), (-18.22pt, -37.84pt), stroke: 0.7pt + black)
  line((-18.22pt, -37.84pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  line((-40.95pt, -9.35pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((32.84pt, 26.19pt), (-32.84pt, 26.19pt), stroke: 0.7pt + black)
  line((-32.84pt, 26.19pt), (-40.95pt, -9.35pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((32.84pt, 26.19pt), text(size: 9pt, fill: black)[b])
  circle((40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((40.95pt, -9.35pt), text(size: 9pt, fill: black)[c])
  circle((18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((18.22pt, -37.84pt), text(size: 9pt, fill: black)[d])
  circle((-18.22pt, -37.84pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-18.22pt, -37.84pt), text(size: 9pt, fill: black)[e])
  circle((-40.95pt, -9.35pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-40.95pt, -9.35pt), text(size: 9pt, fill: black)[f])
  circle((-32.84pt, 26.19pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-32.84pt, 26.19pt), text(size: 9pt, fill: black)[g])
})]),
  alt: "A graph. The graph has seven vertices: a, b, c, d, e, f, and g. The edges connect a b, b c, c d, d e, e f, f a, b g, and g f.", caption: [Graph #emph[H]],
)


      
      #solutionbox[
In order to avoid missing a cycle, begin by analyzing the vertex #emph[a], then proceed in alphabetical order. Vertex #emph[a] is part of two cycles, the quadrilateral cycle (#emph[a], #emph[b], #emph[f], #emph[g],) and the hexagonal cycle (#emph[a], #emph[b], #emph[c], #emph[d], #emph[e], #emph[f]). Next look at vertex #emph[b]. It is part of the hexagonal cycle (#emph[b], #emph[c], #emph[d], #emph[e], #emph[f], #emph[g]). After checking each of the remaining vertices, we see there are no other cycles.
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[In order to avoid naming the same cycle twice, consider naming cycles beginning with the letter closest to the beginning of the alphabet and then progressing clockwise.]
]


    
    We have seen that sociologists use graphs to study the structures of social networks. In sociology, there is a principle known as Triadic Closure. It says that if two individuals in a social network have a friend in common, then it is more likely those two individuals will become friends too. Sociologists refer to this as an open triad becoming a closed triad. This concept can be visualized as graphs in . (Chakraborty, Dutta, Mondal, and Nath, "Application of Graph Theory in Social Media, #emph[International Journal of Computer Sciences and Engineering], 6(10):722-729) In the open triad in , person #emph[a] and person #emph[b] each has a friendship with person #emph[c]. In the closed triad, person #emph[a] and person #emph[b] have also developed a friendship. Notice that the graph representing the closed triad is a three-cycle, or a triangle, in graph theory terms.


    #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)[open triad])
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[b])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[closed triad])
  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])
})]
)]),
  alt: "Two graphs represent the open triad and closed triad. The first graph shows three vertices, a, b, and c. The edges connect a c and c b. The second graph shows the same vertices. The edges connect a c, c b, and b a.", caption: [Graphs of Open Triad and Closed Triad],
)


    Another topic of interest to sociologists, as well as computer scientists and scientists in many fields, is the concept of a #strong[clique]. In a social group, a clique is a subgroup who are all friends. A triad is an example of a clique with three people, but there can be cliques of any size. In graph theory, a clique is a complete subgraph.


    #examplebox("Example 6")[Identifying Triads and Cliques][
The graphs in YOUR TURN 12.6 represent social communities. The vertices are individuals and the edges are social connections. Use the graphs to answer the questions.


        + Which graph has the most triads? Name the triangles.
+ Which graph has the fewest triads? Name the triangles.
+ How might an increase in the number of triads in a graph affect the resilience of a community? Explain your reasoning.
+ Identify a clique with more than three vertices in Graph #emph[E] by naming its vertices.


      
      #solutionbox[
+ Graph #emph[E] has the most triads. The triangles are (#emph[a, b, c]), (#emph[a, c, e]), (#emph[a, c, f]), (#emph[a, c, g]), (#emph[a, e, g]), (#emph[c, e, g]), (#emph[e, g, h]), (#emph[e, h, i]), and (#emph[f, g, i]).
+ Graph #emph[D] has the fewest triads. There are no triangles in the graph.
+ More triads means vertices of greater degree, which indicates greater resilience. Specifically, if an edge is removed from a closed triad, there the two individuals who are no longer adjacent are still connected by way of the third member of the triad.
+ The vertices #emph[a, e, c,] and #emph[g] form a clique with four vertices.
]
]


    
  
  
    
=== Three-Cycles in Complete Graphs


    Just as complete graphs have a predictable number of edges, complete graphs have a predictable number of cyclic subgraphs. Let’s look at the three-cycles within complete graphs with up to six vertices, which are shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[b])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.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), (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)
  line((-39.94pt, 12.98pt), (0.00pt, 42.00pt), 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((39.94pt, 12.98pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((39.94pt, 12.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-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])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})]
)]),
  alt: "Four graphs. The first graph shows three vertices, a, b, and c. The edges connect a c, a b, and c b. The second graph shows four vertices, a, b, c, and d. The edges connect a b, b c, c d, a d, a c, and b d. The third graph shows five vertices, a, b, c, d, and e. The edges connect a b, b c, c d, d e, e a, a d, a c, b e, b d, and c e. The fourth graph shows six vertices, a, b, c, d, e, and f. All the vertices are interconnected using 15 edges.", caption: [Complete Graphs with Up to Six Vertices],
)


    Let's list the names of all the triangles in each graph. #emph[#strong[Since every pair of vertices is adjacent, any three vertices on a complete graph form a triangle]]. There is only one triangle in the complete graph with three vertices, (#emph[a], #emph[b], #emph[c]). For the rest of the graphs, it is important that we take an organized approach. Start with the vertex that is first alphabetically, listing any triangles that include that vertex also in alphabetical order. Then, proceed to the next vertex in the alphabet, and list any triangles that include that vertex, except those that are already listed. Keep going in this way as shown.


    #figure(table(
  columns: 5, align: left, inset: 6pt,
  table.header([Complete Graph With:], [3 Vertices], [4 Vertices], [5 Vertices], [6 Vertices]),
  [All #emph[a] triangles], [(#emph[a], #emph[b], #emph[c])], [(#emph[a, b, c]), (#emph[a, b, d]), #linebreak()  (#emph[a, c, d])], [(#emph[a, b, c]), (#emph[a, b, d]), (#emph[a, b, e]) #linebreak()  (#emph[a, c, d]), (#emph[a, c, e]) #linebreak()  (#emph[a, d, e])], [(#emph[a, b, c]), (#emph[a, b, d]), (#emph[a, b, e]), (#emph[a, b, f]) #linebreak()  (#emph[a, c, d]), (#emph[a, c, e]), (#emph[a, c, f]) #linebreak()  (#emph[a, d, e]), (#emph[a, d, f]) #linebreak()  (#emph[a, e, f])],
  [Other #emph[b] triangles], [None], [(#emph[b, c, d])], [(#emph[b, c, d]), (#emph[b, c, e]), #linebreak()  (#emph[b, d, e])], [(#emph[b, c, d]), (#emph[b, c, e]), (#emph[b, c, f]) #linebreak()  (#emph[b, d, e]), (#emph[b, d, f]) #linebreak() 	 (#emph[b, e, f])],
  [Other #emph[c] triangles], [None], [None], [(#emph[c, d, e])], [(#emph[c, d, e]), (#emph[c, d, f]) #linebreak() 
    (#emph[c, e, f])],
  [Other #emph[d] triangles], [None], [None], [None], [(#emph[d, e, f])],
  [Total], [1], [#math.equation(block: false, alt: "open parenthesis 2 plus 1 close parenthesis plus 1; equals 3 plus 1; equals 4")[$( 2 + 1 ) + 1 \ = 3 + 1 \ = 4$]], [#math.equation(block: false, alt: "open parenthesis 3 plus 2 plus 1 close parenthesis plus open parenthesis 2 plus 1 close parenthesis plus 1; equals 6 plus 3 plus 1; equals 10")[$( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 \ = 6 + 3 + 1 \ = 10$]], [#math.equation(block: false, alt: "open parenthesis 4 plus 3 plus 2 plus 1 close parenthesis plus open parenthesis 3 plus 2 plus 1 close parenthesis plus open parenthesis 2 plus 1 close parenthesis plus 1; equals 10 plus 6 plus 3 plus 1; equals 20")[$( 4 + 3 + 2 + 1 ) + ( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 \ = 10 + 6 + 3 + 1 \ = 20$]],
))


    Look at the last row in . Do you see a pattern emerge for counting triangles in a complete graph? Without drawing a complete graph with 7 vertices, we can predict that it will have #math.equation(block: false, alt: "open parenthesis 5 plus 4 plus 3 plus 2 plus 1 close parenthesis plus open parenthesis 4 plus 3 plus 2 plus 1 close parenthesis plus open parenthesis 3 plus 2 plus 1 close parenthesis plus open parenthesis 2 plus 1 close parenthesis plus 1 equals 35")[$( 5 + 4 + 3 + 2 + 1 ) + ( 4 + 3 + 2 + 1 ) + ( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 = 35$] triangles inside it. This pattern also appears in a famous diagram known to Western mathematicians as "Pascal’s Triangle."  displays the first 11 rows of Pascal’s Triangle. Row 0 of Pascal’s Triangle only has the number 1 in it. The first and last entries in each of the other rows are also 1s. Otherwise, all the entries are formed by adding two entries from the previous row. For example, in row 6, entry 1 is 6, which was found by adding 1 and the 5 from the previous row, and entry 2 is 15, which was found by adding the 5 and the 10 from the previous row, as shown.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 185.61pt), (92.81pt, 160.74pt), stroke: 0.7pt + black)
  circle((0.00pt, 185.61pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((9.00pt, 212.11pt), anchor: "south", text(size: 9pt)[1 in row 1])
  circle((92.81pt, 160.74pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((113.51pt, 182.30pt), anchor: "south-west", text(size: 9pt)[1s in row 2])
  circle((160.74pt, 92.81pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((160.74pt, 92.81pt), text(size: 9pt, fill: black)[35])
  circle((185.61pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((192.61pt, 0.00pt), anchor: "west", text(size: 9pt)[1 in row 6])
  circle((160.74pt, -92.81pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((183.89pt, -102.74pt), anchor: "north-west", text(size: 9pt)[5 in row 5])
  circle((92.81pt, -160.74pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((113.51pt, -182.30pt), anchor: "north-west", text(size: 9pt)[10 in row 5])
  circle((0.00pt, -185.61pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((9.00pt, -212.11pt), anchor: "north", text(size: 9pt)[35 in row 7])
  circle((-92.81pt, -160.74pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-113.51pt, -182.30pt), anchor: "north-east", text(size: 9pt)[Entry 3 in row 7])
  circle((-160.74pt, -92.81pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-183.89pt, -102.74pt), anchor: "north-east", text(size: 9pt)[entry 0 is 1])
  circle((-185.61pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-192.61pt, -0.00pt), anchor: "east", text(size: 9pt)[entry 1 is 10])
  circle((-160.74pt, 92.81pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-183.89pt, 102.74pt), anchor: "south-east", text(size: 9pt)[entry 2 is 45])
  circle((-92.81pt, 160.74pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-113.51pt, 182.30pt), anchor: "south-east", text(size: 9pt)[entry 3 is 120])
  line((93.75pt, 163.16pt), (88.94pt, 161.78pt), (92.41pt, 158.18pt), fill: black, stroke: none, close: true)
})]),
  alt: "Pascal's triangle with 10 rows. Row 0: 1. Row 1: 1, 1. Row 2: 1, 2, 1. Row 3: 1, 3, 3, 1. Row 4: 1, 4, 6, 4, 1. Row 5: 1, 5, 10, 10, 5, 1. Row 6: 1, 6, 15, 20, 15, 6, 1. Row 7: 1, 7, 21, 35, 35, 21, 7, 1. Row 8: 1, 8, 28, 56, 70, 56, 28, 8, 1. Row 9: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1. Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1. 6 in row 6 is achieved by adding 1 and 5 in row 5. 15 in row 6 is achieved by adding 5 and 10 in row 5. Arrows from 1 in row 1 point to the 1s in row 2. Row 7 is outlined. In row 10, entry 0 is 1, entry 1 is 10, entry 2 is 45, entry 3 is 120, and so on. The entry 3 diagonal is outlined. 35 is highlighted. Entry 3 in row 7 is the number of triangles (cycles of size 3) in a complete graph with 7 vertices.", caption: [Pascal’s Triangle],
)


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[IMPORTANT! When you count the rows and entries of Pascal’s Triangle begin with row 0 and entry 0, not row 1 and entry 1.]
]


    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Wajdi_Mohamed_Ratemi")[The Mathematical Secrets of Pascal's Triangle by Wajdi Mohamed Ratemi]
]


    If we begin to list the third entries in each row of Pascal's triangle from the top down, we see 1, 4, 10, 20, 35, and so on. Notice that these values are exactly the number of triangles in a complete graph of sizes 3, 4, 5, 6, and 7, respectively. Specifically, entry 3 in row 7 is 35, the number of triangles in a complete graph of size 7. Let's practice using Pascal’s triangle to find the number of triangles in a complete graph of a particular size.


    #strong[STEPS TO FIND THE NUMBER OF TRIANGLES IN A COMPLETE GRAPH OF SIZE #emph[n]]


    #strong[Step 1] Calculate the entries in row #emph[n] of Pascal's Triangle using sums of pairs of entries in previous rows as needed.


    #strong[Step 2] The number of triangles is entry 3 in row #emph[n]. Remember to count the entries 0, 1, 2, and 3, from left to right.


    #examplebox("Example 7")[Using Pascal’s Triangle to Find the Number of Triangles in a Complete Graph][
Use Pascal’s Triangle in  to find the number of triangles in a complete graph with 11 vertices.


      
      #solutionbox[
#strong[Step 1:] Identify the row number and calculate its entries. Since the complete graph has 11 vertices, we will need to look in row 11 of Pascal’s Triangle. Use row 10 in  to find the entries in row 11 as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 75.54pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[Rows 10 and 11 of Pascal′s triangle])
  line((23.08pt, 46.15pt), (15.38pt, 15.38pt), stroke: 0.7pt + black)
  line((15.38pt, 15.38pt), (19.27pt, 20.60pt), (14.41pt, 21.81pt), close: true, fill: black, stroke: 0.7pt + black)
  line((23.08pt, 46.15pt), (30.77pt, 15.38pt), stroke: 0.7pt + black)
  line((30.77pt, 15.38pt), (31.74pt, 21.81pt), (26.89pt, 20.60pt), close: true, fill: black, stroke: 0.7pt + black)
  line((38.46pt, 46.15pt), (30.77pt, 15.38pt), stroke: 0.7pt + black)
  line((30.77pt, 15.38pt), (34.65pt, 20.60pt), (29.80pt, 21.81pt), close: true, fill: black, stroke: 0.7pt + black)
  line((38.46pt, 46.15pt), (46.15pt, 15.38pt), stroke: 0.7pt + black)
  line((46.15pt, 15.38pt), (47.12pt, 21.81pt), (42.27pt, 20.60pt), close: true, fill: black, stroke: 0.7pt + black)
  line((53.85pt, 46.15pt), (46.15pt, 15.38pt), stroke: 0.7pt + black)
  line((46.15pt, 15.38pt), (50.03pt, 20.60pt), (45.18pt, 21.81pt), close: true, fill: black, stroke: 0.7pt + black)
  line((53.85pt, 46.15pt), (61.54pt, 15.38pt), stroke: 0.7pt + black)
  line((61.54pt, 15.38pt), (62.51pt, 21.81pt), (57.66pt, 20.60pt), close: true, fill: black, stroke: 0.7pt + black)
  content((23.08pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((38.46pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[10]]])
  content((53.85pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[45]]])
  content((69.23pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[120]]])
  content((84.62pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[210]]])
  content((100.00pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[252]]])
  content((115.38pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[210]]])
  content((130.77pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[120]]])
  content((146.15pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[45]]])
  content((161.54pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[10]]])
  content((176.92pt, 46.15pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((15.38pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((30.77pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[11]]])
  content((46.15pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[55]]])
  content((61.54pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[165]]])
  content((76.92pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[330]]])
  content((92.31pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[462]]])
  content((107.69pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[462]]])
  content((123.08pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[330]]])
  content((138.46pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[165]]])
  content((153.85pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[55]]])
  content((169.23pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[11]]])
  content((184.62pt, 15.38pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((7.69pt, 46.15pt), anchor: "east", text(size: 9pt)[Row 10:])
  content((7.69pt, 15.38pt), anchor: "east", text(size: 9pt)[Row 11:])
})]),
  alt: "Rows 10 and 11 of Pascal's triangle. Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, and 1. Row 11: 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, and 1. Arrows from the first number of row 10 point to the first two numbers of row 11 and so on.", caption: [Rows 10 and 11 of Pascal’s Triangle],
)


        #strong[Step 2:] Find entry number 3. The number of triangles is in entry 3. Remember to count the entries beginning with entry 0 as shown.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((100.00pt, 80.67pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 11pt)[Rows 10 and 11 of Pascal′s triangle])
  line((16.67pt, 58.33pt), (8.33pt, 25.00pt), stroke: 0.7pt + black)
  line((8.33pt, 25.00pt), (12.21pt, 30.21pt), (7.36pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((16.67pt, 58.33pt), (25.00pt, 25.00pt), stroke: 0.7pt + black)
  line((25.00pt, 25.00pt), (25.97pt, 31.43pt), (21.12pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((33.33pt, 58.33pt), (25.00pt, 25.00pt), stroke: 0.7pt + black)
  line((25.00pt, 25.00pt), (28.88pt, 30.21pt), (24.03pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((33.33pt, 58.33pt), (41.67pt, 25.00pt), stroke: 0.7pt + black)
  line((41.67pt, 25.00pt), (42.64pt, 31.43pt), (37.79pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((50.00pt, 58.33pt), (41.67pt, 25.00pt), stroke: 0.7pt + black)
  line((41.67pt, 25.00pt), (45.55pt, 30.21pt), (40.70pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((50.00pt, 58.33pt), (58.33pt, 25.00pt), stroke: 0.7pt + black)
  line((58.33pt, 25.00pt), (59.30pt, 31.43pt), (54.45pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((66.67pt, 58.33pt), (58.33pt, 25.00pt), stroke: 0.7pt + black)
  line((58.33pt, 25.00pt), (62.21pt, 30.21pt), (57.36pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((66.67pt, 58.33pt), (75.00pt, 25.00pt), stroke: 0.7pt + black)
  line((75.00pt, 25.00pt), (75.97pt, 31.43pt), (71.12pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((83.33pt, 58.33pt), (75.00pt, 25.00pt), stroke: 0.7pt + black)
  line((75.00pt, 25.00pt), (78.88pt, 30.21pt), (74.03pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((83.33pt, 58.33pt), (91.67pt, 25.00pt), stroke: 0.7pt + black)
  line((91.67pt, 25.00pt), (92.64pt, 31.43pt), (87.79pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((100.00pt, 58.33pt), (91.67pt, 25.00pt), stroke: 0.7pt + black)
  line((91.67pt, 25.00pt), (95.55pt, 30.21pt), (90.70pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((100.00pt, 58.33pt), (108.33pt, 25.00pt), stroke: 0.7pt + black)
  line((108.33pt, 25.00pt), (109.30pt, 31.43pt), (104.45pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((116.67pt, 58.33pt), (108.33pt, 25.00pt), stroke: 0.7pt + black)
  line((108.33pt, 25.00pt), (112.21pt, 30.21pt), (107.36pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((116.67pt, 58.33pt), (125.00pt, 25.00pt), stroke: 0.7pt + black)
  line((125.00pt, 25.00pt), (125.97pt, 31.43pt), (121.12pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((133.33pt, 58.33pt), (125.00pt, 25.00pt), stroke: 0.7pt + black)
  line((125.00pt, 25.00pt), (128.88pt, 30.21pt), (124.03pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((133.33pt, 58.33pt), (141.67pt, 25.00pt), stroke: 0.7pt + black)
  line((141.67pt, 25.00pt), (142.64pt, 31.43pt), (137.79pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((150.00pt, 58.33pt), (141.67pt, 25.00pt), stroke: 0.7pt + black)
  line((141.67pt, 25.00pt), (145.55pt, 30.21pt), (140.70pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((150.00pt, 58.33pt), (158.33pt, 25.00pt), stroke: 0.7pt + black)
  line((158.33pt, 25.00pt), (159.30pt, 31.43pt), (154.45pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((166.67pt, 58.33pt), (158.33pt, 25.00pt), stroke: 0.7pt + black)
  line((158.33pt, 25.00pt), (162.21pt, 30.21pt), (157.36pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((166.67pt, 58.33pt), (175.00pt, 25.00pt), stroke: 0.7pt + black)
  line((175.00pt, 25.00pt), (175.97pt, 31.43pt), (171.12pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  line((183.33pt, 58.33pt), (175.00pt, 25.00pt), stroke: 0.7pt + black)
  line((175.00pt, 25.00pt), (178.88pt, 30.21pt), (174.03pt, 31.43pt), close: true, fill: black, stroke: 0.7pt + black)
  line((183.33pt, 58.33pt), (191.67pt, 25.00pt), stroke: 0.7pt + black)
  line((191.67pt, 25.00pt), (192.64pt, 31.43pt), (187.79pt, 30.21pt), close: true, fill: black, stroke: 0.7pt + black)
  content((16.67pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((33.33pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[10]]])
  content((50.00pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[45]]])
  content((66.67pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[120]]])
  content((83.33pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[210]]])
  content((100.00pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[252]]])
  content((116.67pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[210]]])
  content((133.33pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[120]]])
  content((150.00pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[45]]])
  content((166.67pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[10]]])
  content((183.33pt, 58.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((8.33pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((25.00pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[11]]])
  content((41.67pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[55]]])
  content((58.33pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[165]]])
  content((75.00pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[330]]])
  content((91.67pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[462]]])
  content((108.33pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[462]]])
  content((125.00pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[330]]])
  content((141.67pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[165]]])
  content((158.33pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[55]]])
  content((175.00pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[11]]])
  content((191.67pt, 25.00pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((8.33pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[0]]])
  content((25.00pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[1]]])
  content((41.67pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[2]]])
  content((58.33pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[3]]])
  content((75.00pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[4]]])
  content((91.67pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[5]]])
  content((108.33pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[6]]])
  content((125.00pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[7]]])
  content((141.67pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[8]]])
  content((158.33pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[9]]])
  content((175.00pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[10]]])
  content((191.67pt, 8.33pt), anchor: "center", box(width: 16.00pt)[#align(center)[#text(size: 9pt)[11]]])
})]),
  alt: "Rows 10 and 11 of Pascal's triangle. Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, and 1. Row 11: 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, and 1. The entries of row 11 are numbered from 0 to 11. Arrows from the first number of row 10 point to the first two numbers of row 11 and so on.", caption: [Identifying an Entry in Pascal’s Triangle],
)


        Entry 3 in row 11 is 165. So, there are 165 triangles in a complete graph with 11 vertices.
]
]


    
    #notebox("Tech Check", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
Since the entries in Pascal’s Triangle are useful in many applications, many resources such as online and traditional calculator functions have been developed to assist in calculating the values. The website #link("https://openstax.org/r/has_a_tool")[dCode.xyz has a tool] that automatically calculates entries in Pascal’s Triangle using these steps:


      #strong[Step 1:] Make sure to select Index 0.


      #strong[Step 2:] Select your preference, display the triangle until a particular row (line), display only one row (line), or calculate the value at coordinates (which means give the value of a single entry).


      #strong[Step 3:] Enter row number (line number) you are interested, or enter the row number and entry number in parentheses: (row number, entry number).


      #strong[Step 4:] Select Calculate.


      #strong[Step 5:] Retrieve the answer from the results box.


      #figure(figph[A screenshot of Pascal's triangle. The left section displays a search tool with results: 55. This section is numbered 5. The right section shows two sections titled, Pascal triangle calculator and Position of a number in Pascal triangle. The first section displays the following information. Display the triangle until line: 8. Display only line number: 11. Calculate only the value at coordinates (line, column): (11, 9) (numbered 3). These 3 options are numbered 2. Index: 0, the first row is noted 0. This is numbered 1. Calculate button is present. This is numbered 4. The second section shows the value to search set to 210. Index: 0, the first row is noted 0. Calculate button is present.], alt: "A screenshot of Pascal's triangle. The left section displays a search tool with results: 55. This section is numbered 5. The right section shows two sections titled, Pascal triangle calculator and Position of a number in Pascal triangle. The first section displays the following information. Display the triangle until line: 8. Display only line number: 11. Calculate only the value at coordinates (line, column): (11, 9) (numbered 3). These 3 options are numbered 2. Index: 0, the first row is noted 0. This is numbered 1. Calculate button is present. This is numbered 4. The second section shows the value to search set to 210. Index: 0, the first row is noted 0. Calculate button is present.", caption: [Pascal's Triangle Tool on dCode.xyz])
]


  
  
  
  
    
=== Key Terms


    - complete
- subgraph
- cycle
- cyclic subgraph
- clique


  
  
    
=== Key Concepts


    - The sum of the degrees of the vertices in a graph is twice the number of edges.
- In a complete graph every pair of vertices is adjacent.
- A subgraph is part of a larger graph.
- Cycles are a sequence of connected vertices that begin and end at the same vertex but never visit any vertex twice.


  
  
    
=== Formulas


    For the Sum of Degrees Theorem, #math.equation(block: false, alt: "sum of the degrees equals 2 times number of edges")[$"sum of the degrees" = 2 × "number of edges"$] or #math.equation(block: false, alt: "number of edges equals the fraction sum of degrees over 2")[$"number of edges" = frac("sum of degrees", 2)$]


    The number of edges in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is the sum of the whole numbers from 1 to #math.equation(block: false, alt: "n minus 1")[$n − 1$], #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus open parenthesis n minus 1 close parenthesis")[$1 + 2 + 3 + ⋯ + ( n − 1 )$].


    The number of edges in a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices is #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus open parenthesis n minus 1 close parenthesis equals the fraction n open parenthesis n minus 1 close parenthesis over 2")[$1 + 2 + 3 + ⋯ + ( n − 1 ) = frac(n ( n − 1 ), 2)$].


  
  
    
=== Videos


    - #link("https://openstax.org/r/Wajdi_Mohamed_Ratemi")[The Mathematical Secrets of Pascal's Triangle by Wajdi Mohamed Ratemi]