#set document(title: "12.1 Graph Basics", 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.1#h(0.6em)Graph Basics


  #figure(figph[A close-up view of three people holding cell phones.], alt: "A close-up view of three people holding cell phones.", caption: [Cell phone networks connect individuals.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Identify parts of a graph.
+ Model applications of graph basics.


  
  When you hear the word, #emph[graph], what comes to mind? You might think of the #math.equation(block: false, alt: "xy")[$italic("xy")$]-coordinate system you learned about earlier in this course, or you might think of the line graphs and bar charts that are used to display data in news reports. The graphs we discuss in this chapter are probably very different from what you think of as a graph. They look like a bunch of dots connected by short line segments. The dots represent a group of objects and the line segments represent the connections, or relationships, between them. The objects might be bus stops, computers, Snapchat accounts, family members, or any other objects that have direct connections to each other. The connections can be physical or virtual, formal or casual, scientific or social. Regardless of the kind of connections, the purpose of the graph is to help us visualize the structure of the entire network to better understand the interactions of the objects within it.


  
    
=== Parts of a Graph


    In a #strong[graph], the objects are represented with dots and their connections are represented with lines like those in .  displays a #strong[simple graph] labeled #emph[G] and a #strong[multigraph] labeled #emph[H]. The dots are called #strong[vertices]; an individual dot is a #strong[vertex], which is one object of a set of objects, some of which may be connected. We often label vertices with letters. For example, Graph #emph[G] has vertices #emph[a, b, c], and #emph[d], and Multigraph #emph[H] has vertices, #emph[e, f, g], and #emph[h]. Each line segment or connection joining two vertices is referred to as an #strong[edge]. #emph[H] is considered a multigraph because it has a double edge between #emph[f] and #emph[h], and a double edge between #emph[h] and #emph[g]. Another reason #emph[H] is called a multigraph is that it has a #strong[loop] connecting vertex #emph[e] to itself; a loop is an edge that joins a vertex to itself. Loops and double edges are not allowed in a simple graph.


    To sum up, a simple graph is a collection of vertices and any edges that may connect them, such that every edge connects two vertices with no loops and no two vertices are joined by more than one edge. A multigraph is a graph in which there may be loops or pairs of vertices that are joined by more than one edge. In this chapter, most of our work will be with simple graphs, which we will call graphs for convenience.


    #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)[G])
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[b])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[c])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[d])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 83.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[H])
  bezier((42.00pt, 0.00pt), (-42.00pt, -0.00pt), (-0.00pt, 4.20pt), stroke: 0.7pt + black)
  bezier((42.00pt, 0.00pt), (-42.00pt, -0.00pt), (0.00pt, -4.20pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-23.97pt, -23.97pt), stroke: 0.7pt + black)
  bezier((-42.00pt, -0.00pt), (0.00pt, -42.00pt), (-18.03pt, -18.03pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 55.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)[e])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[f])
  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])
})]
)]),
  alt: "Two graphs are labeled graph G and multigraph H. Graph G has four vertices, a, b, c, and d. Two edges connect a with b and c. Two edges connect c with b and d. Multigraph H has four vertices, e, f, g, and h. A double edge connects f and h. A double edge connects h and g. Two edges connect e with f and h. A loop connects vertex e to itself.", caption: [A Graph and a Multigraph],
)


    It is not necessary for the edges in a graph to be straight. In fact, you can draw an edge any way you want. In graph theory, the focus is on which vertices are connected, not how the connections are drawn. In a graph, each edge can be named by the two letters of the associated vertices. The four edges in Graph #emph[X] in  are #emph[ab, ac, ad], and #emph[ae]. The order of the letters is not important when you name the edge of a graph. For example, #emph[ab] refers to the same edge as #emph[ba].


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[A graph may have vertices that are not joined to other vertices by edges, such as vertex f in Graph X in , but any edge must have a vertex at each end.]
]


    #figure(
  stdfig([#grid(columns: 2, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph X])
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((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)
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[a])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[b])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[c])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[d])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[e])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[f])
})],
  [#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph X])
  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)
  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: "Two graphs are labeled graph X. In each graph, six vertices are present: a, b, c, d, e, and f. Edges connect a with b, c, d, and e. In the first graph, the edges are straight lines. In the second graph, the edges are curved.", caption: [Different Representations of the Same Graph],
)


    #examplebox("Example 1")[Identifying Edges and Vertices][
Name all the vertices and edges of graph #emph[F] in .


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph F])
  line((24.69pt, -33.98pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (39.94pt, 12.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((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)[V])
  circle((39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[W])
  circle((24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[X])
  circle((-24.69pt, -33.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[Y])
  circle((-39.94pt, 12.98pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[Z])
})]),
  alt: "A graph labeled graph F. The graph has five vertices: V, W, X, Y, and Z. Four edges connect X with V, W, Y, and Z. Two edges connect W with V and Z.", caption: [Graph #emph[F]],
)


      
      #solutionbox[
The vertices are #emph[v, w, x, y], and #emph[z]. The edges are #emph[vw, vx, wx, wz, xy], and #emph[xz].
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[When listing the vertices and edges in a graph, work in alphabetical order to avoid accidentally listing the same item twice. When you are finished, count the number of vertices or edges you listed and compare that to the number of vertices or edges on the graph to ensure you didn’t miss any.]
]


    
    Since the purpose of a graph is to represent the connections between objects, it is very important to know if two vertices share a common edge. The two vertices at either end of a given edge are referred to as #strong[neighboring], or #strong[adjacent]. For example, in , vertices #emph[x] and #emph[w] are adjacent, but vertices #emph[y] and #emph[w] are not.


    #examplebox("Example 2")[Identifying Vertices That Are Not Adjacent][
Name all the pairs of vertices of graph #emph[F] in  that are #emph[not] adjacent.


      
      #solutionbox[
The pairs of vertices that are not adjacent in graph #emph[F] are #emph[v] and #emph[y, v] and #emph[z, w] and #emph[y], and #emph[y] and #emph[z].
]
]


    
    #notebox("People in Mathematics", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Sergey Brin and Laurence Page]


      The “Google boys,” Sergey Brin and Laurence Page, transformed the World Wide Web in 1998 when they used the mathematics of graph theory to create an algorithm called Page Rank, which is known as the Google Search Engine today. The two computer scientists identified webpages as vertices and hyperlinks on those pages as edges because hyperlinks connect one website to the next. The number of edges influences the ranking of a website on the Google Search Engine because the websites with more links to “credible sources” are ranked higher. #link("https://openstax.org/r/The_Graph_Theory")[("Page Rank: The Graph Theory-based Backbone of Google,"] September 20, 2011, Cornell University, Networks Blog.
]


  
  
    
=== Analyzing Geographical Maps with Graphs


    #figure(figph[A map shows dots representing the flight connections from a particular airport.], alt: "A map shows dots representing the flight connections from a particular airport.", caption: [Commercial airlines' route systems create a global network.])


    When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in . Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In , the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex FYW has #strong[degree] 3. The degree of a vertex is the number of edges that connect to that vertex.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((-24.69pt, -33.98pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (39.94pt, 12.98pt), 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((39.94pt, 12.98pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((39.94pt, 12.98pt), text(size: 9pt, fill: black)[EYW])
  circle((24.69pt, -33.98pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((24.69pt, -33.98pt), text(size: 9pt, fill: black)[MIA])
  circle((-24.69pt, -33.98pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-24.69pt, -33.98pt), text(size: 9pt, fill: black)[FLL])
  circle((-39.94pt, 12.98pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-39.94pt, 12.98pt), text(size: 9pt, fill: black)[PBI])
})]),
  alt: "A graph represents the direct flights between South Florida airports. The graph has five vertices. Edges from the vertex, Tampa T P A connect 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 Fort Lauderdale with Key West. An edge connects Miami with Key West.", caption: [Direct Flights between South Florida Airports],
)


    #examplebox("Example 3")[Determining the Degree of a Vertex][
Determine the degree of each vertex of Graph #emph[J] in . If graph #emph[J] represents direct flights between a set of airports, do any of the airports have direct flights to two or more of the other cities on the graph?


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 63.00pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[graph J])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  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: "A graph labeled graph J. The graph has five vertices, a, b, c, d, and e. Edges connect a with b, c, and d. An edge connects c with d.", caption: [Graph #emph[J]],
)


      
      #solutionbox[
For each vertex, count the number of edges that meet at that vertex. This value is the degree of the vertex. In , the dashed edges indicate the edges that meet at the marked vertex.


        #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 J])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  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)[graph J])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  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)[graph J])
  line((0.00pt, 42.00pt), (39.94pt, 12.98pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (24.69pt, -33.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  line((0.00pt, 42.00pt), (-24.69pt, -33.98pt), stroke: 0.7pt + black)
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  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)[graph J])
  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: (paint: black, thickness: 0.7pt, dash: "dotted"))
  line((24.69pt, -33.98pt), (-24.69pt, -33.98pt), stroke: (paint: black, thickness: 0.7pt, dash: "dotted"))
  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)[graph J])
  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((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])
})]
)]),
  alt: "Five graphs labeled graph J. In the first graph vertex a has degree 3. The graph has five vertices, a, b, c, d, and e. Dotted edges from a connect with b, c, and d. An edge connects c with d. In the second graph vertex b has degree 1. The graph has five vertices, a, b, c, d, and e. Edges from a connect with b, c, and d. An edge connects c with d. The edge connecting b and a is dotted. In the third graph vertex c has degree 2. The graph has five vertices, a, b, c, d, and e. Edges from a connect with b, c, and d. An edge connects c with d. The edges connecting a and c and c and d are dotted. In the fourth graph vertex d has degree 2. The graph has five vertices, a, b, c, d, and e. Edges from a connect with b, c, and d. An edge connects c with d. The edges connecting c and d and a and d are dotted. In the fifth graph vertex e has degree 0. The graph has five vertices, a, b, c, d, and e. Edges from a connect with b, c, and d. An edge connects c with d.", caption: [Degrees of Vertices of Graph #emph[J]],
)


        Vertex #emph[a] has degree 3, vertex #emph[b] has degree 1, vertices #emph[c] and #emph[d] each have degree 2, and vertex #emph[e] has degree 0. Airports #emph[a, c,] and #emph[d] have direct flights to two or more of the other airports.
]
]


    
    Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the “Four Corners,” which is shown in the map in .


    #figure(figph[A map of the USA with the four corners region highlighted. It includes Utah, Colorado, Arizona, and New Mexico.], alt: "A map of the USA with the four corners region highlighted. It includes Utah, Colorado, Arizona, and New Mexico.", caption: [Map of the Four Corners])


    In , each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are #emph[not] considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size and distance, toward the existence of the relationship of having a shared boundary.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 43.19pt), (43.19pt, 0.00pt), stroke: 0.7pt + black)
  line((43.19pt, 0.00pt), (0.00pt, -43.19pt), stroke: 0.7pt + black)
  line((0.00pt, -43.19pt), (-43.19pt, -0.00pt), stroke: 0.7pt + black)
  line((-43.19pt, -0.00pt), (0.00pt, 43.19pt), stroke: 0.7pt + black)
  circle((0.00pt, 43.19pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, 61.89pt), anchor: "south", text(size: 9pt)[Utah])
  circle((43.19pt, 0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((50.19pt, 0.00pt), anchor: "west", text(size: 9pt)[Colorado])
  circle((0.00pt, -43.19pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((3.60pt, -61.89pt), anchor: "north", text(size: 9pt)[Arizona])
  circle((-43.19pt, -0.00pt), radius: 3pt, fill: black, stroke: 0.7pt + black)
  content((-50.19pt, -0.00pt), anchor: "east", text(size: 9pt)[NewMexico])
})]),
  alt: "A graph of four corner states. The graph shows four edges and four vertices forming a rectangle. The vertices are Utah, Colorado, Arizona, and New Mexico.", caption: [Graph of the Shared Boundaries of Four Corners States],
)


    #examplebox("Example 4")[Graphing the Midwestern States][
A map of the Midwest is given in . Create a graph of the region in which each vertex represents a state and each edge represents a shared border.


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


      
      #solutionbox[
#strong[Step 1:] For each state, draw and label a vertex as in .


        #figure(figph[A partial map of the USA with the midwestern states. The Midwestern states are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H).], alt: "A partial map of the USA with the midwestern states. The Midwestern states are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H).", caption: [Vertex Assigned to Each Midwestern State])


        #strong[Step 2:] Draw edges between any two states that share a common land border as in .


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


        The graph is given in .


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 45.43pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((0.00pt, 45.43pt), (-26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (43.21pt, 14.04pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((26.71pt, 36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (26.71pt, -36.76pt), stroke: 0.7pt + black)
  line((-26.71pt, -36.76pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((43.21pt, 14.04pt), (43.21pt, -14.04pt), stroke: 0.7pt + black)
  line((43.21pt, -14.04pt), (0.00pt, -45.43pt), stroke: 0.7pt + black)
  line((0.00pt, -45.43pt), (-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((-43.21pt, 14.04pt), (-26.71pt, 36.76pt), stroke: 0.7pt + black)
  circle((0.00pt, 45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 45.43pt), text(size: 9pt, fill: black)[MN])
  circle((26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, 36.76pt), text(size: 9pt, fill: black)[NE])
  circle((43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, 14.04pt), text(size: 9pt, fill: black)[KS])
  circle((43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((43.21pt, -14.04pt), text(size: 9pt, fill: black)[MO])
  circle((26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((26.71pt, -36.76pt), text(size: 9pt, fill: black)[IA])
  circle((0.00pt, -45.43pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -45.43pt), text(size: 9pt, fill: black)[IL])
  circle((-26.71pt, -36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, -36.76pt), text(size: 9pt, fill: black)[WI])
  circle((-43.21pt, -14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, -14.04pt), text(size: 9pt, fill: black)[IN])
  circle((-43.21pt, 14.04pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-43.21pt, 14.04pt), text(size: 9pt, fill: black)[MI])
  circle((-26.71pt, 36.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-26.71pt, 36.76pt), text(size: 9pt, fill: black)[OH])
})]),
  alt: "A graph represents common boundaries between midwestern states. Edges from M N connect with I A and W I. Edges from N E connect with K S, M O, and I A. Edges from I A connect with M O and I L. Edges from W I connect with I A and I L. An edge from K S connects with M O. An edge from M O connects with I L. An edge from I L connects with I N. Edges from I N connect with M I and O H. An edge from M I connects with O H.", caption: [Final Graph Representing Common Boundaries between Midwestern States],
)
]
]


    
    #notebox("Video", rgb("#DC2626"), rgb("#DC2626"), rgb("#f7f8fa"))[
#link("https://openstax.org/r/Graph_Theory")[Graph Theory: Create a Graph to Represent Common Boundaries on a Map]
]


  
  
    
=== Graphs of Social Interactions


    Geographical maps are just one of many real-world scenarios which graphs can depict. Any scenario in which objects are connected to each other can be represented with a graph, and the connections don’t have to be physical. Just think about all the connections you have to people around the world through social media! Who is in your network of Twitter followers? Whose Snapchat network are you connected to?


    #examplebox("Example 5")[Graphing Chloe’s #emph[Roblox] Friends][
Roblox is an online gaming platform. Chloe is interested to know how many people in her network of #emph[Roblox] friends are also friends with each other so she polls them. Explain how a graph or multigraph might be drawn to model this scenario by identifying the objects that could be represented by vertices and the connections that could be represented by edges. Indicate whether a graph or a multigraph would be a better model.


      
      #solutionbox[
The objects that are represented with vertices are #emph[Roblox] friends. A #emph[Roblox] friendship between two friends will be represented as an edge between a pair of vertices. There will be no double edges because it is not possible for two friends to be linked twice in #emph[Roblox]; they are either friends or they are not. Also, a player cannot be a friend to themself, so there is no need for a loop. Since there are no double edges or loops, this is best represented as a graph.
]
]


    
    #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[
#emph[Using Graph Theory to Reduce Internet Fraud]


      Could graphs be used to reduce Internet fraud? At least one researcher thinks so. Graph theory is used every day to analyze our behavior, particularly on social network sites. Alex Buetel, a computer scientist from Carnegie Mellon University in Pittsburgh, Pennsylvania, published a research paper in 2016 that discussed the possibilities of distinguishing the normal interactions from those that might be fraudulent using graph theory. Buetel wrote, “To more effectively model and detect abnormal behavior, we model #emph[how] fraudsters work, catching previously undetected fraud on Facebook, Twitter, and Tencent Weibo and improving classification accuracy by up to 68%.” In the same paper, the researcher discusses how similar techniques can be used to model many other applications and even, “predict #emph[why] you like a particular movie.” (Alex Beutel, "User Behavior Modeling with Large-Scale Graph Analysis," http://reports-archive.adm.cs.cmu.edu/anon/2016/CMU-CS-16-105.pdf, May 2016, CMU-CS-16-105, Computer Science Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA)
]


  
  
  
  
    
=== Key Terms


    - vertex
- edge
- loop
- graph (simple graph)
- multigraph
- adjacent (neighboring)
- degree


  
  
    
=== Key Concepts


    - Graphs and multigraphs represent objects as vertices and the relationships between the objects as edges.
- The degree of a vertex is the number of edges that meet it and the degree can be zero.
- An edge must have a vertex at each end.
- Multigraphs may contain loops and double edges, but simple graphs may not.


  
  
    
=== Videos


    - #link("https://openstax.org/r/Graph_Theory")[Graph Theory: Create a Graph to Represent Common Boundaries on a Map]