#set document(title: "5.1 Definitions", 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")) == 5.1#h(0.6em)Definitions #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Which (if any) of the graphs below are the same? #figure(figph[A graph with five vertices arranged in as a row of two on top and three on bottom. Edges connect each vertex in the top row to each vertex in the bottom row.], alt: "A graph with five vertices arranged in as a row of two on top and three on bottom. Edges connect each vertex in the top row to each vertex in the bottom row.", caption: none) #figure(figph[A graph with five vertices arranged in a pentagon. Each vertex is connected to its two neighbors around the pentagon by edges.], alt: "A graph with five vertices arranged in a pentagon. Each vertex is connected to its two neighbors around the pentagon by edges.", caption: none) #figure(figph[A graph with five vertices arranged in a diamond with one vertex in the middle. The top vertex is connected to the two outside vertices below it, which are connected to the bottom vertex. The center vertex is connected to the two vertices to its left and right.], alt: "A graph with five vertices arranged in a diamond with one vertex in the middle. The top vertex is connected to the two outside vertices below it, which are connected to the bottom vertex. The center vertex is connected to the two vertices to its left and right.", caption: none) #figure(figph[A graph with five vertices arranged in a pentagon, with edges connecting each vertex to the two vertices farthest away from it (forming a 5-pointed star).], alt: "A graph with five vertices arranged in a pentagon, with edges connecting each vertex to the two vertices farthest away from it (forming a 5-pointed star).", caption: none) #figure(figph[Five vertices arranged as a diamond with one vertex in the center. The center vertex has edges between it and each of the other vertices.], alt: "Five vertices arranged as a diamond with one vertex in the center. The center vertex has edges between it and each of the other vertices.", caption: none) The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same? #figure(figph[A graph with six vertices arranged in two rows of three. The top vertices are labeled b, d, f from left to right. The bottom vertices are labeled a, c, e from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges cross from a top vertex to a bottom vertex just to the left or right (forming two X's).], alt: "A graph with six vertices arranged in two rows of three. The top vertices are labeled b, d, f from left to right. The bottom vertices are labeled a, c, e from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges cross from a top vertex to a bottom vertex just to the left or right (forming two X's).", caption: none) #figure(figph[A graph with six vertices arranged in two rows of three. The top vertices are labeled b, c, f from left to right. The bottom vertices are labeled a, d, e from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges connect vertices along the top row and along the bottom row. Together this looks like two adjacent squares.], alt: "A graph with six vertices arranged in two rows of three. The top vertices are labeled b, c, f from left to right. The bottom vertices are labeled a, d, e from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges connect vertices along the top row and along the bottom row. Together this looks like two adjacent squares.", caption: none) #figure(figph[A graph with six vertices arranged in two rows of three. The top vertices are labeled c, b, f from left to right. The bottom vertices are labeled a, e, d from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges cross from a top vertex to a bottom vertex just to the left or right (forming two X's).], alt: "A graph with six vertices arranged in two rows of three. The top vertices are labeled c, b, f from left to right. The bottom vertices are labeled a, e, d from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges cross from a top vertex to a bottom vertex just to the left or right (forming two X's).", caption: none) #figure(figph[A graph with six vertices arranged in two rows of three. The top vertices are labeled v1, v2, v3 from left to right. The bottom vertices are labeled b6, v5, v4 from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges connect vertices along the top row and along the bottom row. Together this looks like two adjacent squares.], alt: "A graph with six vertices arranged in two rows of three. The top vertices are labeled v1, v2, v3 from left to right. The bottom vertices are labeled b6, v5, v4 from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges connect vertices along the top row and along the bottom row. Together this looks like two adjacent squares.", caption: none) Actually, all the graphs we have seen above are just #emph[drawings] of graphs. A graph is really an abstract mathematical object consisting of two sets #math.equation(block: false, alt: "V")[$V$] and #math.equation(block: false, alt: "E")[$E$] where #math.equation(block: false, alt: "E")[$E$] is a set of 2-element subsets of #math.equation(block: false, alt: "V")[$V$]. Are the graphs below the same or different? - #strong[Graph 1:] #linebreak() #math.equation(block: false, alt: "V equals open brace a , b , c , d , e close brace")[$V = \{ a , b , c , d , e \}$], #linebreak() #math.equation(block: false, alt: "E equals open brace open brace a , b close brace , open brace a , c close brace , open brace a , d close brace , open brace a , e close brace , open brace b , c close brace , open brace d , e close brace close brace")[$E = \{ \{ a , b \} , \{ a , c \} , \{ a , d \} , \{ a , e \} , \{ b , c \} , \{ d , e \} \}$]. - #strong[Graph 2:] #linebreak() #math.equation(block: false, alt: "V equals open brace v sub 1 , v sub 2 , v sub 3 , v sub 4 , v sub 5 close brace")[$V = \{ v_(1) , v_(2) , v_(3) , v_(4) , v_(5) \}$], #linebreak() #math.equation(block: false, alt: "E equals open brace open brace v sub 1 , v sub 3 close brace , open brace v sub 1 , v sub 5 close brace , open brace v sub 2 , v sub 4 close brace , open brace v sub 2 , v sub 5 close brace , open brace v sub 3 , v sub 5 close brace , open brace v sub 4 , v sub 5 close brace close brace")[$E = \{ \{ v_(1) , v_(3) \} , \{ v_(1) , v_(5) \} , \{ v_(2) , v_(4) \} , \{ v_(2) , v_(5) \} , \{ v_(3) , v_(5) \} , \{ v_(4) , v_(5) \} \}$]. ] Before we start studying graphs, we need to agree upon what a graph is. While we almost always think of graphs as pictures (dots connected by lines) this is fairly ambiguous. Do the lines need to be straight? Does it matter how long the lines are or how large the dots are? Can there be two lines connecting the same pair of dots? Can one line connect three dots? The way we avoid ambiguities in mathematics is to provide concrete and rigorous #emph[definitions]. Crafting good definitions is not easy, but it is incredibly important. The definition is the agreed upon starting point from which all truths in mathematics proceed. Is there a graph with no edges? We have to look at the definition to see if this is possible. We want our definition to be precise and unambiguous, but it also must agree with our intuition for the objects we are studying. It needs to be useful: we #emph[could] define a graph to be a six legged mammal, but that would not let us solve any problems about bridges. Instead, here is the (now) standard definition of a graph. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Graph Definition] A #strong[graph] is an ordered pair #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$] consisting of a nonempty set #math.equation(block: false, alt: "V")[$V$] (called the #strong[vertices]) and a set #math.equation(block: false, alt: "E")[$E$] (called the #strong[edges]) of two-element subsets of #math.equation(block: false, alt: "V")[$V$]. ] Strange. Nowhere in the definition is there talk of dots or lines. From the definition, a graph could be #math.equation(block: true, alt: "open parenthesis open brace a , b , c , d close brace , open brace open brace a , b close brace , open brace a , c close brace , open brace b , c close brace , open brace b , d close brace , open brace c , d close brace close brace close parenthesis")[$( \{ a , b , c , d \} , \{ \{ a , b \} , \{ a , c \} , \{ b , c \} , \{ b , d \} , \{ c , d \} \} )$] . Here we have a graph with four vertices (the letters #math.equation(block: false, alt: "a , b , c , d")[$a , b , c , d$]) and five edges (the pairs #math.equation(block: false, alt: "open brace a , b close brace , open brace a , c close brace , open brace b , c close brace , open brace b , d close brace , open brace c , d close brace close parenthesis")[$\{ a , b \} , \{ a , c \} , \{ b , c \} , \{ b , d \} , \{ c , d \} \)$]). Looking at sets and sets of 2-element sets is difficult to process. That is why we often draw a representation of these sets. We put a dot down for each vertex, and connect two dots with a line precisely when those two vertices are one of the 2-element subsets in our set of edges. Thus one way to draw the graph described above is this: #figure(figph[Four vertices arranged in a square, with edges on the border of the square and one connecting the bottom left vertex to the top right vertex. Vertices are labeled a (top left), b (top right), c (bottom left) and d (bottom right).], alt: "Four vertices arranged in a square, with edges on the border of the square and one connecting the bottom left vertex to the top right vertex. Vertices are labeled a (top left), b (top right), c (bottom left) and d (bottom right).", caption: none) However we could also have drawn the graph differently. For example either of these: #figure(figph[Four vertices arranged in a square. Vertices are labeled a (top left), d (top right), c (bottom left) and b (bottom right). Edges connect a to c and b, d to b and c, and c to b.], alt: "Four vertices arranged in a square. Vertices are labeled a (top left), d (top right), c (bottom left) and b (bottom right). Edges connect a to c and b, d to b and c, and c to b.", caption: none) #figure(figph[Four vertices arranged in a horizontal row, labeled a, b, c, and d from left to right. Edges connect each vertex to the one on its right. A curved edge connects a to c, and another curved edge connects b to d.], alt: "Four vertices arranged in a horizontal row, labeled a, b, c, and d from left to right. Edges connect each vertex to the one on its right. A curved edge connects a to c, and another curved edge connects b to d.", caption: none) We should be careful about what it means for two graphs to be “the same.” Actually, given our definition, this is easy: Are the vertex sets equal? Are the edge sets equal? We know what it means for sets to be equal, and graphs are nothing but a pair of two special sorts of sets. #examplebox("Example 1")[][ Are the graphs below equal? #math.equation(block: true, alt: "G sub 1 equals open parenthesis open brace a , b , c close brace , open brace open brace a , b close brace , open brace b , c close brace close brace close parenthesis ; G sub 2 equals open parenthesis open brace a , b , c close brace , open brace open brace a , c close brace , open brace c , b close brace close brace close parenthesis")[$G_(1) = ( \{ a , b , c \} , \{ \{ a , b \} , \{ b , c \} \} ) ; #h(2em) G_(2) = ( \{ a , b , c \} , \{ \{ a , c \} , \{ c , b \} \} )$] . #solutionbox[ No. Here the vertex sets of each graph are equal, which is a good start. Also, both graphs have two edges. In the first graph, we have edges #math.equation(block: false, alt: "open brace a , b close brace")[$\{ a , b \}$] and #math.equation(block: false, alt: "open brace b , c close brace")[$\{ b , c \}$], while in the second graph we have edges #math.equation(block: false, alt: "open brace a , c close brace")[$\{ a , c \}$] and #math.equation(block: false, alt: "open brace c , b close brace")[$\{ c , b \}$]. Now we do have #math.equation(block: false, alt: "open brace b , c close brace equals open brace c , b close brace")[$\{ b , c \} = \{ c , b \}$], so that is not the problem. The issue is that #math.equation(block: false, alt: "open brace a , b close brace not equal to open brace a , c close brace")[$\{ a , b \} ≠ \{ a , c \}$]. Since the edge sets of the two graphs are not equal (as sets), the graphs are not equal (as graphs). ] ] Even if two graphs are not #emph[equal], they might be #emph[basically] the same. The graphs in the previous example could be drawn like this: #figure(figph[Two graphs with three vertices each arranged in a horizontal row. Edges connect vertices to the vertex on either side of it. The graph on the left (G1) has vertices labeled a, b, c from left to right. The graph on the right (G2) has vertices labeled a, c, b from left to right.], alt: "Two graphs with three vertices each arranged in a horizontal row. Edges connect vertices to the vertex on either side of it. The graph on the left (G1) has vertices labeled a, b, c from left to right. The graph on the right (G2) has vertices labeled a, c, b from left to right.", caption: none) Graphs that are basically the same (but perhaps not equal) are called #strong[isomorphic]. We will give a precise definition of this term after a quick example: #examplebox("Example 2")[][ Consider the graphs: #math.equation(block: true, alt: "G sub 1 equals open parenthesis V sub 1 , E sub 1 close parenthesis where V sub 1 equals open brace a , b , c close brace and E sub 1 equals open brace open brace a , b close brace , open brace a , c close brace , open brace b , c close brace close brace ;")[$G_(1) = ( V_(1) , E_(1) ) " where " V_(1) = \{ a , b , c \} " and " E_(1) = \{ \{ a , b \} , \{ a , c \} , \{ b , c \} \} ;$] #math.equation(block: true, alt: "G sub 2 equals open parenthesis V sub 2 , E sub 2 close parenthesis where V sub 2 equals open brace u , v , w close brace and E sub 2 equals open brace open brace u , v close brace , open brace u , w close brace , open brace v , w close brace close brace .")[$G_(2) = ( V_(2) , E_(2) ) " where " V_(2) = \{ u , v , w \} " and " E_(2) = \{ \{ u , v \} , \{ u , w \} , \{ v , w \} \} .$] Are these graphs the same? #solutionbox[ The two graphs are NOT equal. It is enough to notice that #math.equation(block: false, alt: "V sub 1 not equal to V sub 2")[$V_(1) ≠ V_(2)$] since #math.equation(block: false, alt: "a ∈ V sub 1")[$a ∈ V_(1)$] but #math.equation(block: false, alt: "a ∉ V sub 2")[$a ∉ V_(2)$]. However, both of these graphs consist of three vertices with edges connecting every pair of vertices. We can draw them as follows: #figure(figph[A graph with three vertices arranged as a triangle, with edges along the border of the triangle. The vertices are labeled a, b, and c.], alt: "A graph with three vertices arranged as a triangle, with edges along the border of the triangle. The vertices are labeled a, b, and c.", caption: none) #figure(figph[A graph with three vertices arranged as a triangle, with edges along the border of the triangle. The vertices are labeled u, v, and w.], alt: "A graph with three vertices arranged as a triangle, with edges along the border of the triangle. The vertices are labeled u, v, and w.", caption: none) Clearly we want to say these graphs are basically the same, so while they are not equal, they will be #emph[isomorphic]. We can rename the vertices of one graph and get the second graph as the result. ] ] Intuitively, graphs are #strong[isomorphic] if they are basically the same, or better yet, if they are the same except for the names of the vertices. To make the concept of renaming vertices precise, we give the following definitions: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Isomorphic Graphs] An #strong[isomorphism] between two graphs #math.equation(block: false, alt: "G sub 1")[$G_(1)$] and #math.equation(block: false, alt: "G sub 2")[$G_(2)$] is a bijection #math.equation(block: false, alt: "f : V sub 1 → V sub 2")[$f : V_(1) → V_(2)$] between the vertices of the graphs such that #math.equation(block: false, alt: "open brace a , b close brace")[$\{ a , b \}$] is an edge in #math.equation(block: false, alt: "G sub 1")[$G_(1)$] if and only if #math.equation(block: false, alt: "open brace f open parenthesis a close parenthesis , f open parenthesis b close parenthesis close brace")[$\{ f ( a ) , f ( b ) \}$] is an edge in #math.equation(block: false, alt: "G sub 2")[$G_(2)$]. Two graphs are #strong[isomorphic] if there is an isomorphism between them. In this case we write #math.equation(block: false, alt: "G sub 1 ≅ G sub 2")[$G_(1) ≅ G_(2)$]. ] An isomorphism is simply a function which renames the vertices. It must be a bijection so every vertex gets a new name. These newly named vertices must be connected by edges precisely when they were connected by edges with their old names. #examplebox("Example 3")[][ Decide whether the graphs #math.equation(block: false, alt: "G sub 1 equals open parenthesis V sub 1 , E sub 1 close parenthesis")[$G_(1) = ( V_(1) , E_(1) )$] and #math.equation(block: false, alt: "G sub 2 equals open parenthesis V sub 2 , E sub 2 close parenthesis")[$G_(2) = ( V_(2) , E_(2) )$] are equal or isomorphic. #math.equation(block: true, alt: "V sub 1 equals open brace a , b , c , d close brace")[$V_(1) = \{ a , b , c , d \}$], #math.equation(block: true, alt: "E sub 1 equals open brace open brace a , b close brace , open brace a , c close brace , open brace a , d close brace , open brace c , d close brace close brace")[$E_(1) = \{ \{ a , b \} , \{ a , c \} , \{ a , d \} , \{ c , d \} \}$] #math.equation(block: true, alt: "V sub 2 equals open brace a , b , c , d close brace")[$V_(2) = \{ a , b , c , d \}$], #math.equation(block: true, alt: "E sub 2 equals open brace open brace a , b close brace , open brace a , c close brace , open brace b , c close brace , open brace c , d close brace close brace")[$E_(2) = \{ \{ a , b \} , \{ a , c \} , \{ b , c \} , \{ c , d \} \}$] #solutionbox[ The graphs are NOT equal, since #math.equation(block: false, alt: "open brace a , d close brace ∈ E sub 1")[$\{ a , d \} ∈ E_(1)$] but #math.equation(block: false, alt: "open brace a , d close brace ∉ E sub 2")[$\{ a , d \} ∉ E_(2)$]. However, since both graphs contain the same number of vertices and same number of edges, they #emph[might] be isomorphic (this is not enough in most cases, but it is a good start). We can try to build an isomorphism. How about we say #math.equation(block: false, alt: "f open parenthesis a close parenthesis equals b")[$f ( a ) = b$], #math.equation(block: false, alt: "f open parenthesis b close parenthesis equals c")[$f ( b ) = c$], #math.equation(block: false, alt: "f open parenthesis c close parenthesis equals d")[$f ( c ) = d$] and #math.equation(block: false, alt: "f open parenthesis d close parenthesis equals a")[$f ( d ) = a$]. This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it #emph[respects the edge relation]. In #math.equation(block: false, alt: "G sub 1")[$G_(1)$], vertices #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are connected by an edge. In #math.equation(block: false, alt: "G sub 2")[$G_(2)$], #math.equation(block: false, alt: "f open parenthesis a close parenthesis equals b")[$f ( a ) = b$] and #math.equation(block: false, alt: "f open parenthesis b close parenthesis equals c")[$f ( b ) = c$] are connected by an edge. So far, so good, but we must check the other three edges. The edge #math.equation(block: false, alt: "open brace a , c close brace")[$\{ a , c \}$] in #math.equation(block: false, alt: "G sub 1")[$G_(1)$] corresponds to #math.equation(block: false, alt: "open brace f open parenthesis a close parenthesis , f open parenthesis c close parenthesis close brace equals open brace b , d close brace")[$\{ f ( a ) , f ( c ) \} = \{ b , d \}$], but here we have a problem. There is no edge between #math.equation(block: false, alt: "b")[$b$] and #math.equation(block: false, alt: "d")[$d$] in #math.equation(block: false, alt: "G sub 2")[$G_(2)$]. Thus #math.equation(block: false, alt: "f")[$f$] is NOT an isomorphism. Not all hope is lost, however. Just because #math.equation(block: false, alt: "f")[$f$] is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up. #figure(figph[The graph G1 with four vertices arranged in a diamond. The top vertex (a) is connected to the three other vertices (d on the left, b on the right, and c below). There is one additional edge between d and c.], alt: "The graph G1 with four vertices arranged in a diamond. The top vertex (a) is connected to the three other vertices (d on the left, b on the right, and c below). There is one additional edge between d and c.", caption: none) #figure(figph[The graph G2 with four vertices arranged in a diamond. The top vertex (a) is connected to the the vertices c below and b on the right. There is two additional edges between d (left) and c and between b and c .], alt: "The graph G2 with four vertices arranged in a diamond. The top vertex (a) is connected to the the vertices c below and b on the right. There is two additional edges between d (left) and c and between b and c .", caption: none) Alternatively, notice that in #math.equation(block: false, alt: "G sub 1")[$G_(1)$], the vertex #math.equation(block: false, alt: "a")[$a$] is adjacent to every other vertex. In #math.equation(block: false, alt: "G sub 2")[$G_(2)$], there is also a vertex with this property: #math.equation(block: false, alt: "c")[$c$]. So build the bijection #math.equation(block: false, alt: "g : V sub 1 → V sub 2")[$g : V_(1) → V_(2)$] by defining #math.equation(block: false, alt: "g open parenthesis a close parenthesis equals c")[$g ( a ) = c$] to start with. Next, where should we send #math.equation(block: false, alt: "b")[$b$]? In #math.equation(block: false, alt: "G sub 1")[$G_(1)$], the vertex #math.equation(block: false, alt: "b")[$b$] is only adjacent to vertex #math.equation(block: false, alt: "a")[$a$]. There is exactly one vertex like this in #math.equation(block: false, alt: "G sub 2")[$G_(2)$], namely #math.equation(block: false, alt: "d")[$d$]. So let #math.equation(block: false, alt: "g open parenthesis b close parenthesis equals d")[$g ( b ) = d$]. As for the last two, in this example, we have a free choice: let #math.equation(block: false, alt: "g open parenthesis c close parenthesis equals b")[$g ( c ) = b$] and #math.equation(block: false, alt: "g open parenthesis d close parenthesis equals a")[$g ( d ) = a$] (switching these would be fine as well). We should check that this really is an isomorphism. It is definitely a bijection. We must make sure that the edges are respected. The four edges in #math.equation(block: false, alt: "G sub 1")[$G_(1)$] are #math.equation(block: true, alt: "open brace a , b close brace , open brace a , c close brace , open brace a , d close brace , open brace c , d close brace")[$\{ a , b \} , \{ a , c \} , \{ a , d \} , \{ c , d \}$] . Under the proposed isomorphism these become #math.equation(block: true, alt: "open brace g open parenthesis a close parenthesis , g open parenthesis b close parenthesis close brace , open brace g open parenthesis a close parenthesis , g open parenthesis c close parenthesis close brace , open brace g open parenthesis a close parenthesis , g open parenthesis d close parenthesis close brace , open brace g open parenthesis c close parenthesis , g open parenthesis d close parenthesis close brace")[$\{ g ( a ) , g ( b ) \} , \{ g ( a ) , g ( c ) \} , \{ g ( a ) , g ( d ) \} , \{ g ( c ) , g ( d ) \}$] #math.equation(block: true, alt: "open brace c , d close brace , open brace c , b close brace , open brace c , a close brace , open brace b , a close brace")[$\{ c , d \} , \{ c , b \} , \{ c , a \} , \{ b , a \}$] , which are precisely the edges in #math.equation(block: false, alt: "G sub 2")[$G_(2)$]. Thus #math.equation(block: false, alt: "g")[$g$] is an isomorphism, so #math.equation(block: false, alt: "G sub 1 ≅ G sub 2")[$G_(1) ≅ G_(2)$] ] ] Sometimes we will talk about a graph with a special name (like #math.equation(block: false, alt: "K sub n")[$K_(n)$] or the #emph[Petersen graph]) or perhaps draw a graph without any labels. In this case we are really referring to #emph[all] graphs isomorphic to any copy of that particular graph. A collection of isomorphic graphs is often called an #strong[isomorphism class]. This is not unlike geometry, where we might have more than one copy of a particular triangle. There instead of #emph[isomorphic] we say #emph[congruent]. There are other relationships between graphs that we care about, other than equality and being isomorphic. For example, compare the following pair of graphs: #figure(figph[A graph with six vertices arranged in a hexagon, with edges between every possible pair of vertices.], alt: "A graph with six vertices arranged in a hexagon, with edges between every possible pair of vertices.", caption: none) #figure(figph[Four vertices arranged in a diamond, with edges between every possible pair of vertices.], alt: "Four vertices arranged in a diamond, with edges between every possible pair of vertices.", caption: none) These are definitely not isomorphic, but notice that the graph on the right looks like it might be part of the graph on the left, especially if we draw it like this: #figure(figph[A graph with six vertices arranged in a hexagon with edges between every pair of vertices. Six edges are drawn in bold, forming a slanted rectangle with an X through it.], alt: "A graph with six vertices arranged in a hexagon with edges between every pair of vertices. Six edges are drawn in bold, forming a slanted rectangle with an X through it.", caption: none) We would like to say that the smaller graph is a #emph[subgraph] of the larger. We should give a careful definition of this. In fact, there are two reasonable notions for what a subgraph should mean. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Subgraphs] We say that #math.equation(block: false, alt: "G prime equals open parenthesis V prime , E prime close parenthesis")[$G^(′) = ( V^(′) , E^(′) )$] is a #strong[subgraph] of #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$], and write #math.equation(block: false, alt: "G prime ⊆ G")[$G^(′) ⊆ G$], provided #math.equation(block: false, alt: "V prime ⊆ V")[$V^(′) ⊆ V$] and #math.equation(block: false, alt: "E prime ⊆ E")[$E^(′) ⊆ E$]. We say that #math.equation(block: false, alt: "G prime equals open parenthesis V prime , E prime close parenthesis")[$G^(′) = ( V^(′) , E^(′) )$] is an #strong[induced subgraph] of #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$] provided #math.equation(block: false, alt: "V prime ⊆ V")[$V^(′) ⊆ V$] and every edge in #math.equation(block: false, alt: "E")[$E$] whose vertices are still in #math.equation(block: false, alt: "V prime")[$V^(′)$] is also an edge in #math.equation(block: false, alt: "E prime")[$E^(′)$]. ] Notice that every induced subgraph is also an ordinary subgraph, but not conversely. Think of a subgraph as the result of deleting some vertices and edges from the larger graph. For the subgraph to be an induced subgraph, we can still delete vertices, but now we only delete those edges that included the deleted vertices. #examplebox("Example 4")[][ Consider the graphs: #figure(figph[The graph G1 consisting of six vertices arranged in a triangle. Starting with the bottom left vertex and traveling around the triangle clockwise, the vertices are labeled a, d, f, e, c, b. Edges connect vertices at the corners of the triangle to vertices along their edges of the triangle. These center vertices are also connected to each of the other center vertices.], alt: "The graph G1 consisting of six vertices arranged in a triangle. Starting with the bottom left vertex and traveling around the triangle clockwise, the vertices are labeled a, d, f, e, c, b. Edges connect vertices at the corners of the triangle to vertices along their edges of the triangle. These center vertices are also connected to each of the other center vertices.", caption: none) #figure(figph[The graph G2 of four vertices: a horizontal row of three, labeled a, b, c, and a vertex labeled d centered between and above a and b. Edges connect a, b, and d (forming a triangle) and a fourth edge connects b to c.], alt: "The graph G2 of four vertices: a horizontal row of three, labeled a, b, c, and a vertex labeled d centered between and above a and b. Edges connect a, b, and d (forming a triangle) and a fourth edge connects b to c.", caption: none) #figure(figph[The graph G3 of five vertices. Vertices a, b, and c are aligned in a horizontal row. Vertices d and f form a line with a in a line that slants up and to the right. There are edges between a and d, between d and f, between d and b, and between b and c.], alt: "The graph G3 of five vertices. Vertices a, b, and c are aligned in a horizontal row. Vertices d and f form a line with a in a line that slants up and to the right. There are edges between a and d, between d and f, between d and b, and between b and c.", caption: none) #figure(figph[The graph G4 with five vertices: a, b, and c form a horizontal row, d and f line up with a in a line slanting up and the to the right. The vertices form a triangle, and edges are arranged to fill in the outside border of the triangle. Vertices d and b are also connected by and edge.], alt: "The graph G4 with five vertices: a, b, and c form a horizontal row, d and f line up with a in a line slanting up and the to the right. The vertices form a triangle, and edges are arranged to fill in the outside border of the triangle. Vertices d and b are also connected by and edge.", caption: none) Here both #math.equation(block: false, alt: "G sub 2")[$G_(2)$] and #math.equation(block: false, alt: "G sub 3")[$G_(3)$] are subgraphs of #math.equation(block: false, alt: "G sub 1")[$G_(1)$]. But only #math.equation(block: false, alt: "G sub 2")[$G_(2)$] is an #emph[induced] subgraph. Every edge in #math.equation(block: false, alt: "G sub 1")[$G_(1)$] that connects vertices in #math.equation(block: false, alt: "G sub 2")[$G_(2)$] is also an edge in #math.equation(block: false, alt: "G sub 2")[$G_(2)$]. In #math.equation(block: false, alt: "G sub 3")[$G_(3)$], the edge #math.equation(block: false, alt: "open brace a , b close brace")[$\{ a , b \}$] is in #math.equation(block: false, alt: "E sub 1")[$E_(1)$] but not #math.equation(block: false, alt: "E sub 3")[$E_(3)$], even though vertices #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are in #math.equation(block: false, alt: "V sub 3")[$V_(3)$]. The graph #math.equation(block: false, alt: "G sub 4")[$G_(4)$] is NOT a subgraph of #math.equation(block: false, alt: "G sub 1")[$G_(1)$], even though it looks like all we did is remove vertex #math.equation(block: false, alt: "e")[$e$]. The reason is that in #math.equation(block: false, alt: "E sub 4")[$E_(4)$] we have the edge #math.equation(block: false, alt: "open brace c , f close brace")[$\{ c , f \}$] but this is not an element of #math.equation(block: false, alt: "E sub 1")[$E_(1)$], so we don't have the required #math.equation(block: false, alt: "E sub 4 ⊆ E sub 1")[$E_(4) ⊆ E_(1)$]. ] Back to some basic graph theory definitions. Notice that all the graphs we have drawn above have the property that no pair of vertices is connected more than once, and no vertex is connected to itself. Graphs like these are sometimes called #strong[simple], although we will just call them #emph[graphs]. This is because our definition for a graph says that the edges form a set of 2-element subsets of the vertices. Remember that it doesn't make sense to say a set contains an element more than once. So no pair of vertices can be connected by an edge more than once. Also, since each edge must be a set containing two vertices, we cannot have a single vertex connected to itself by an edge. That said, there are times we want to consider double (or more) edges and single edge loops. For example, the “graph” we drew for the Bridges of Königsberg problem had double edges because there really are two bridges connecting a particular island to the near shore. We will call these objects #strong[multigraphs]. This is a good name: a #emph[multiset] is a set in which we are allowed to include a single element multiple times. The graphs above are also #strong[connected]: you can get from any vertex to any other vertex by following some path of edges. A graph that is not connected can be thought of as two separate graphs drawn close together. For example, the following graph is NOT connected because there is no path from #math.equation(block: false, alt: "a")[$a$] to #math.equation(block: false, alt: "b")[$b$]: #figure(figph[A graph consisting of eight vertices arranged in two overlapping diamonds, with edges forming the border of those diamonds. The vertex on the far left is labeled a and the vertex on the far right is labeled b.], alt: "A graph consisting of eight vertices arranged in two overlapping diamonds, with edges forming the border of those diamonds. The vertex on the far left is labeled a and the vertex on the far right is labeled b.", caption: none) Vertices in a graph do not always have edges between them. If we add all possible edges, then the resulting graph is called #strong[complete]. That is, a graph is complete if every pair of vertices is connected by an edge. Since a graph is determined completely by which vertices are adjacent to which other vertices, there is only one complete graph with a given number of vertices. We give these a special name: #math.equation(block: false, alt: "K sub n")[$K_(n)$] is the complete graph on #math.equation(block: false, alt: "n")[$n$] vertices. Each vertex in #math.equation(block: false, alt: "K sub n")[$K_(n)$] is adjacent to #math.equation(block: false, alt: "n minus 1")[$n − 1$] other vertices. We call the number of edges emanating from a given vertex the #strong[degree] of that vertex. So every vertex in #math.equation(block: false, alt: "K sub n")[$K_(n)$] has degree #math.equation(block: false, alt: "n minus 1")[$n − 1$]. How many edges does #math.equation(block: false, alt: "K sub n")[$K_(n)$] have? One might think the answer should be #math.equation(block: false, alt: "n open parenthesis n minus 1 close parenthesis")[$n ( n − 1 )$], since we count #math.equation(block: false, alt: "n minus 1")[$n − 1$] edges #math.equation(block: false, alt: "n")[$n$] times (once for each vertex). However, each edge is incident to 2 vertices, so we counted every edge exactly twice. Thus there are #math.equation(block: false, alt: "n open parenthesis n minus 1 close parenthesis / 2")[$n ( n − 1 ) / 2$] edges in #math.equation(block: false, alt: "K sub n")[$K_(n)$]. Alternatively, we can say there are #math.equation(block: false, alt: "open parenthesis the fraction n over 2 close parenthesis")[$( binom(n, 2) )$] edges, since to draw an edge we must choose 2 of the #math.equation(block: false, alt: "n")[$n$] vertices. In general, if we know the degrees of all the vertices in a graph, we can find the number of edges. The sum of the degrees of all vertices will always be #emph[twice] the number of edges, since each edge adds to the degree of two vertices. Notice this means that the sum of the degrees of all vertices in any graph must be even! This is our first example of a general result about all graphs. It seems innocent enough, but we will use it to prove all sorts of other statements. So let's give it a name and state it formally. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Handshake Lemma] In any graph, the sum of the degrees of vertices in the graph is always twice the number of edges. ] The handshake lemmaA #emph[lemma] is a mathematical statement that is primarily of importance in that it is used to establish other results. is sometimes called the #emph[degree sum formula], and can be written symbolically as #math.equation(block: true, alt: "∑ v ∈ V d open parenthesis v close parenthesis equals 2 e")[$limits(∑)_(v ∈ V) d ( v ) = 2 e$] . Here we are using the notation #math.equation(block: false, alt: "d open parenthesis v close parenthesis")[$d ( v )$] for the degree of the vertex #math.equation(block: false, alt: "v")[$v$]. One use for the lemma is to actually find the number of edges in a graph. To do this, you must be given the #strong[degree sequence] for the graph (or be able to find it from other information). This is a list of every degree of every vertex in the graph, generally written in non-increasing order. #examplebox("Example 5")[][ How many vertices and edges must a graph have if its degree sequence is #math.equation(block: true, alt: "open parenthesis 4 , 4 , 3 , 3 , 3 , 2 , 1 close parenthesis")[$( 4 , 4 , 3 , 3 , 3 , 2 , 1 )$] ? #solutionbox[ The number of vertices is easy to find: it is the number of degrees in the sequence: 7. To find the number of edges, we compute the degree sum: #math.equation(block: true, alt: "4 plus 4 plus 3 plus 3 plus 3 plus 2 plus 1 equals 20")[$4 + 4 + 3 + 3 + 3 + 2 + 1 = 20$] , so the number of edges is half this: 10. ] ] The handshake lemma also tells us what is not possible. #examplebox("Example 6")[][ At a recent math seminar, 9 mathematicians greeted each other by shaking hands. Is it possible that each mathematician shook hands with exactly 7 people at the seminar? #solutionbox[ It seems like this should be possible. Each mathematician chooses one person to not shake hands with. But this cannot happen. We are asking whether a graph with 9 vertices can have each vertex have degree 7. If such a graph existed, the sum of the degrees of the vertices would be #math.equation(block: false, alt: "9 times 7 equals 63")[$9 ⋅ 7 = 63$]. This would be twice the number of edges (handshakes) resulting in a graph with #math.equation(block: false, alt: "31.5")[$31.5$] edges. That is impossible. Thus at least one (in fact an odd number) of the mathematicians must have shaken hands with an #emph[even] number of people at the seminar. ] ] We can generalize the previous example to get the following proposition.A #strong[proposition] is a general statement in mathematics, similar to a theorem, although generally of lesser importance. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ In any graph, the number of vertices with odd degree must be even. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Suppose there were a graph with an odd number of vertices with odd degree. Then the sum of the degrees in the graph would be odd, which is impossible, by the handshake lemma. ] ] We will consider further applications of the handshake lemma in the exercises. One final definition: we say a graph is #strong[bipartite] if the vertices can be divided into two sets, #math.equation(block: false, alt: "A")[$A$] and #math.equation(block: false, alt: "B")[$B$], with no two vertices in #math.equation(block: false, alt: "A")[$A$] adjacent and no two vertices in #math.equation(block: false, alt: "B")[$B$] adjacent. The vertices in #math.equation(block: false, alt: "A")[$A$] can be adjacent to some or all of the vertices in #math.equation(block: false, alt: "B")[$B$]. If each vertex in #math.equation(block: false, alt: "A")[$A$] is adjacent to all the vertices in #math.equation(block: false, alt: "B")[$B$], then the graph is a #strong[complete bipartite graph], and gets a special name: #math.equation(block: false, alt: "K sub m , n")[$K_(m , n)$], where #math.equation(block: false, alt: "vertical bar A vertical bar equals m")[$| A | = m$] and #math.equation(block: false, alt: "vertical bar B vertical bar equals n")[$| B | = n$]. The graph in the houses and utilities puzzle is #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$]. === Named Graphs Some graphs are used more than others, and get special names. - #strong[#math.equation(block: false, alt: "K sub n")[$K_(n)$]] #linebreak() The complete graph on #math.equation(block: false, alt: "n")[$n$] vertices. - #strong[#math.equation(block: false, alt: "K sub m , n")[$K_(m , n)$]] #linebreak() The complete bipartite graph with sets of #math.equation(block: false, alt: "m")[$m$] and #math.equation(block: false, alt: "n")[$n$] vertices. - #strong[#math.equation(block: false, alt: "C sub n")[$C_(n)$]] #linebreak() The cycle on #math.equation(block: false, alt: "n")[$n$] vertices, just one big loop. - #strong[#math.equation(block: false, alt: "P sub n")[$P_(n)$]] #linebreak() The path on #math.equation(block: false, alt: "n plus 1")[$n + 1$] vertices (so #math.equation(block: false, alt: "n")[$n$] edges), just one long path. #figure(figph[The graph K5: five vertices arranged in a pentagon. Each vertex is connected to each other vertex by an edge.], alt: "The graph K5: five vertices arranged in a pentagon. Each vertex is connected to each other vertex by an edge.", caption: none) #figure(figph[The graph K2,3: a row of two vertices on top and three on bottom. Each vertex in the top row is connected to each vertex on the bottom row.], alt: "The graph K2,3: a row of two vertices on top and three on bottom. Each vertex in the top row is connected to each vertex on the bottom row.", caption: none) #figure(figph[The graph C6: a cycle of six vertices connected by six edges arranged as a hexagon.], alt: "The graph C6: a cycle of six vertices connected by six edges arranged as a hexagon.", caption: none) #figure(figph[The graph P5: six vertices connected by five edges. The first and last vertex have one edge, each other vertex has two edges (connecting to the previous and next vertex on the path).], alt: "The graph P5: six vertices connected by five edges. The first and last vertex have one edge, each other vertex has two edges (connecting to the previous and next vertex on the path).", caption: none) === Graph Theory Definitions There are a lot of definitions to keep track of in graph theory. Here is a glossary of the terms we have already used and will soon encounter. - #strong[Graph] #linebreak() A collection of #strong[vertices], some of which are connected by #strong[edges]. More precisely, a pair of sets #math.equation(block: false, alt: "V")[$V$] and #math.equation(block: false, alt: "E")[$E$] where #math.equation(block: false, alt: "V")[$V$] is a set of vertices and #math.equation(block: false, alt: "E")[$E$] is a set of 2-element subsets of #math.equation(block: false, alt: "V")[$V$]. - #strong[Adjacent] #linebreak() Two vertices are #strong[adjacent] if they are connected by an edge. Two edges are #strong[adjacent] if they share a vertex. - #strong[Bipartite graph] #linebreak() A graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set. - #strong[Complete bipartite graph] #linebreak() A bipartite graph for which every vertex in the first set is adjacent to every vertex in the second set. - #strong[Complete graph] #linebreak() A graph in which every pair of vertices is adjacent. - #strong[Connected] #linebreak() A graph is #strong[connected] if there is a path from any vertex to any other vertex. - #strong[Chromatic number] #linebreak() The minimum number of colors required in a proper vertex coloring of the graph. - #strong[Cycle] #linebreak() A path (see below) that starts and stops at the same vertex, but contains no other repeated vertices. - #strong[Degree of a vertex] #linebreak() The number of edges incident to a vertex. - #strong[Euler path] #linebreak() A walk which uses each edge exactly once. - #strong[Euler circuit] #linebreak() An Euler path which starts and stops at the same vertex. - #strong[Multigraph] #linebreak() A #strong[multigraph] is just like a graph but can contain multiple edges between two vertices as well as single edge loops (that is an edge from a vertex to itself). - #strong[Path] #linebreak() A #strong[path] is a walk that doesn't repeat any vertices (or edges) except perhaps the first and last. If a path starts and ends at the same vertex, it is called a #strong[cycle]. - #strong[Planar] #linebreak() A graph which can be drawn (in the plane) without any edges crossing. - #strong[Subgraph] #linebreak() We say that #math.equation(block: false, alt: "H")[$H$] is a #strong[subgraph] of #math.equation(block: false, alt: "G")[$G$] if every vertex and edge of #math.equation(block: false, alt: "H")[$H$] is also a vertex or edge of #math.equation(block: false, alt: "G")[$G$]. We say #math.equation(block: false, alt: "H")[$H$] is an #strong[induced] subgraph of #math.equation(block: false, alt: "G")[$G$] if every vertex of #math.equation(block: false, alt: "H")[$H$] is a vertex of #math.equation(block: false, alt: "G")[$G$] and each pair of vertices in #math.equation(block: false, alt: "H")[$H$] are adjacent in #math.equation(block: false, alt: "H")[$H$] if and only if they are adjacent in #math.equation(block: false, alt: "G")[$G$]. - #strong[Tree] #linebreak() A connected graph with no cycles. (If we remove the requirement that the graph is connected, the graph is called a #strong[forest].) The vertices in a tree with degree 1 are called #strong[leaves]. - #strong[Vertex coloring] #linebreak() An assignment of colors to each of the vertices of a graph. A vertex coloring is #strong[proper] if adjacent vertices are always colored differently. - #strong[Walk] #linebreak() A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no edge is repeated is called a #strong[trail], and a trail in which no vertex is repeated (except possibly the first and last) is called a #strong[path]. If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theory? #solutionbox[ This is asking for the number of edges in #math.equation(block: false, alt: "K sub 10")[$K_(10)$]. Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is #math.equation(block: false, alt: "90")[$90$]. However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place. ] Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group? #solutionbox[ It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph #math.equation(block: false, alt: "C sub 5")[$C_(5)$]). However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even. ] Is it possible for two #emph[different] (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for example)? Draw two such graphs or explain why not. Both situations are possible. Go find some examples. Are the two graphs below equal? Are they isomorphic? If they are isomorphic, give the isomorphism. If not, explain. Graph 1: #math.equation(block: false, alt: "V equals open brace a , b , c , d , e close brace")[$V = \{ a , b , c , d , e \}$], #math.equation(block: false, alt: "E equals open brace open brace a , b close brace , open brace a , c close brace , open brace a , e close brace , open brace b , d close brace , open brace b , e close brace , open brace c , d close brace close brace")[$E = \{ \{ a , b \} , \{ a , c \} , \{ a , e \} , \{ b , d \} , \{ b , e \} , \{ c , d \} \}$]. Graph 2: #figure(figph[A graph with five vertices arranged in a pentagon, labeled a through e, starting with the vertex at the top and proceeding counterclockwise. Edges between vertices a, c, and d make a triangle. Edges between b, c, d, and e form a quadralateral.], alt: "A graph with five vertices arranged in a pentagon, labeled a through e, starting with the vertex at the top and proceeding counterclockwise. Edges between vertices a, c, and d make a triangle. Edges between b, c, d, and e form a quadralateral.", caption: none) #solutionbox[ The graphs are not equal. For example, graph 1 has an edge #math.equation(block: false, alt: "open brace a , b close brace")[$\{ a , b \}$] but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is #math.equation(block: false, alt: "f : G sub 1 → G sub 2")[$f : G_(1) → G_(2)$] defined by #math.equation(block: false, alt: "f open parenthesis a close parenthesis equals d")[$f ( a ) = d$], #math.equation(block: false, alt: "f open parenthesis b close parenthesis equals c")[$f ( b ) = c$], #math.equation(block: false, alt: "f open parenthesis c close parenthesis equals e")[$f ( c ) = e$], #math.equation(block: false, alt: "f open parenthesis d close parenthesis equals b")[$f ( d ) = b$], #math.equation(block: false, alt: "f open parenthesis e close parenthesis equals a")[$f ( e ) = a$]. ] Consider the following two graphs: - #strong[#math.equation(block: false, alt: "G sub 1")[$G_(1)$]] #linebreak() #math.equation(block: false, alt: "V sub 1 equals open brace a , b , c , d , e , f , g close brace")[$V_(1) = \{ a , b , c , d , e , f , g \}$] #linebreak() #math.equation(block: false, alt: "E sub 1 equals open brace open brace a , b close brace , open brace a , d close brace , open brace b , c close brace , open brace b , d close brace , open brace b , e close brace , open brace b , f close brace , open brace c , g close brace , open brace d , e close brace")[$E_(1) = \{ \{ a , b \} , \{ a , d \} , \{ b , c \} , \{ b , d \} , \{ b , e \} , \{ b , f \} , \{ c , g \} , \{ d , e \}$], #linebreak() #math.equation(block: false, alt: "open brace e , f close brace , open brace f , g close brace close brace")[$\{ e , f \} , \{ f , g \} \}$]. - #strong[#math.equation(block: false, alt: "G sub 2")[$G_(2)$]] #linebreak() #math.equation(block: false, alt: "V sub 2 equals open brace v sub 1 , v sub 2 , v sub 3 , v sub 4 , v sub 5 , v sub 6 , v sub 7 close brace")[$V_(2) = \{ v_(1) , v_(2) , v_(3) , v_(4) , v_(5) , v_(6) , v_(7) \}$], #linebreak() #math.equation(block: false, alt: "E sub 2 equals open brace open brace v sub 1 , v sub 4 close brace , open brace v sub 1 , v sub 5 close brace , open brace v sub 1 , v sub 7 close brace , open brace v sub 2 , v sub 3 close brace , open brace v sub 2 , v sub 6 close brace")[$E_(2) = \{ \{ v_(1) , v_(4) \} , \{ v_(1) , v_(5) \} , \{ v_(1) , v_(7) \} , \{ v_(2) , v_(3) \} , \{ v_(2) , v_(6) \}$], #linebreak() #math.equation(block: false, alt: "open brace v sub 3 , v sub 5 close brace , open brace v sub 3 , v sub 7 close brace , open brace v sub 4 , v sub 5 close brace , open brace v sub 5 , v sub 6 close brace , open brace v sub 5 , v sub 7 close brace close brace")[$\{ v_(3) , v_(5) \} , \{ v_(3) , v_(7) \} , \{ v_(4) , v_(5) \} , \{ v_(5) , v_(6) \} , \{ v_(5) , v_(7) \} \}$] + Let #math.equation(block: false, alt: "f : G sub 1 → G sub 2")[$f : G_(1) → G_(2)$] be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table: #figure(table( columns: 8, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "x")[$x$]], [#math.equation(block: false, alt: "a")[$a$]], [#math.equation(block: false, alt: "b")[$b$]], [#math.equation(block: false, alt: "c")[$c$]], [#math.equation(block: false, alt: "d")[$d$]], [#math.equation(block: false, alt: "e")[$e$]], [#math.equation(block: false, alt: "f")[$f$]], [#math.equation(block: false, alt: "g")[$g$]]), [#math.equation(block: false, alt: "f open parenthesis x close parenthesis")[$f ( x )$]], [#math.equation(block: false, alt: "v sub 4")[$v_(4)$]], [#math.equation(block: false, alt: "v sub 5")[$v_(5)$]], [#math.equation(block: false, alt: "v sub 1")[$v_(1)$]], [#math.equation(block: false, alt: "v sub 6")[$v_(6)$]], [#math.equation(block: false, alt: "v sub 2")[$v_(2)$]], [#math.equation(block: false, alt: "v sub 3")[$v_(3)$]], [#math.equation(block: false, alt: "v sub 7")[$v_(7)$]], )) #linebreak() Does #math.equation(block: false, alt: "f")[$f$] define an isomorphism between Graph 1 and Graph 2? + Define a new function #math.equation(block: false, alt: "g")[$g$] (with #math.equation(block: false, alt: "g not equal to f")[$g ≠ f$]) that defines an isomorphism between Graph 1 and Graph 2. + Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain. #figure(figph[A graph with seven vertices. Six of the vertices are arranged in rectangle, three across and two down, with edges around the perimeter. The seventh vertex is in the center, with edges connecting it to the vertices directly above and below it, and to the two outside vertices in the bottom row.], alt: "A graph with seven vertices. Six of the vertices are arranged in rectangle, three across and two down, with edges around the perimeter. The seventh vertex is in the center, with edges connecting it to the vertices directly above and below it, and to the two outside vertices in the bottom row.", caption: none) What is the largest number of edges possible in a graph with 10 vertices? What is the largest number of edges possible in a #emph[bipartite] graph with 10 vertices? What is the largest number of edges possible in a #emph[tree] with 10 vertices? The bipartite graph is a little tricky. You will definitely want a complete bipartite graph, but it could be #math.equation(block: false, alt: "K sub 5 , 5")[$K_(5 , 5)$] or maybe #math.equation(block: false, alt: "K sub 1 , 9")[$K_(1 , 9)$], or … Which of the graphs below are bipartite? Justify your answers. #figure(figph[A graph with five vertices. Four vertices make up the corners of a diamond; the last vertex is in the center. Edges form the perimeter of the diamond and connect the center vertex to the two corners on the left and right.], alt: "A graph with five vertices. Four vertices make up the corners of a diamond; the last vertex is in the center. Edges form the perimeter of the diamond and connect the center vertex to the two corners on the left and right.", caption: none) #figure(figph[A graph consisting of six vertices arranged in a hexagon. Edges connect each vertex to two others, but not in a cycle around the outside of the hexagon. However, following along the edges does visit every vertex.], alt: "A graph consisting of six vertices arranged in a hexagon. Edges connect each vertex to two others, but not in a cycle around the outside of the hexagon. However, following along the edges does visit every vertex.", caption: none) #figure(figph[A graph consisting of seven vertices arranged in a seven-sided polygon, with edges forming the perimeter of the polygon.], alt: "A graph consisting of seven vertices arranged in a seven-sided polygon, with edges forming the perimeter of the polygon.", caption: none) #figure(figph[A graph consisting of a single vertex with eight edges connecting to eight vertices arranged in a circle around the central vertex.], alt: "A graph consisting of a single vertex with eight edges connecting to eight vertices arranged in a circle around the central vertex.", caption: none) The first graph is bipartite, which can be seen by labeling it as follows. #figure(figph[A graph with five vertices. Four vertices make up the corners of a diamond; the last vertex is in the center. Edges form the perimeter of the diamond and connect the center vertex to the two corners on the left and right. The vertices on left and right are labeled A, the three vertices in the center column are each labeled B.], alt: "A graph with five vertices. Four vertices make up the corners of a diamond; the last vertex is in the center. Edges form the perimeter of the diamond and connect the center vertex to the two corners on the left and right. The vertices on left and right are labeled A, the three vertices in the center column are each labeled B.", caption: none) Two of the remaining three are also bipartite. For which #math.equation(block: false, alt: "n greater than or equal to 3")[$n ≥ 3$] is the graph #math.equation(block: false, alt: "C sub n")[$C_(n)$] bipartite? #math.equation(block: false, alt: "C sub 4")[$C_(4)$] is bipartite; #math.equation(block: false, alt: "C sub 5")[$C_(5)$] is not. What about all the other values of #math.equation(block: false, alt: "n")[$n$]? For each of the following, try to give two #emph[different] unlabeled graphs with the given properties, or explain why doing so is impossible. + Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles. + Two different graphs with 8 vertices all of degree 2. + Two different graphs with 5 vertices all of degree 4. + Two different graphs with 5 vertices all of degree 3. #solutionbox[ + For example: #figure(figph[A graph consisting of a vertex with three edges connecting it to three vertices in a row above it.], alt: "A graph consisting of a vertex with three edges connecting it to three vertices in a row above it.", caption: none) #figure(figph[A graph consisting of four vertices arranged in a V. The left point of the V connects to the bottom corner of the V. That vertex is connected to a vertex half way up the right side of the V, which is then connected to the vertex at the right point of the V.], alt: "A graph consisting of four vertices arranged in a V. The left point of the V connects to the bottom corner of the V. That vertex is connected to a vertex half way up the right side of the V, which is then connected to the vertex at the right point of the V.", caption: none) + This is not possible if we require the graphs to be connected. If not, we could take #math.equation(block: false, alt: "C sub 8")[$C_(8)$] as one graph and two copies of #math.equation(block: false, alt: "C sub 4")[$C_(4)$] as the other. + Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph #math.equation(block: false, alt: "K sub 5")[$K_(5)$]. + This is not possible. In fact, there is not even one graph with this property (such a graph would have #math.equation(block: false, alt: "5 times 3 / 2 equals 7.5")[$5 ⋅ 3 / 2 = 7.5$] edges). ] Decide whether the statements below about subgraphs are true or false. For those that are true, briefly explain why (1 or 2 sentences). For any that are false, give a counterexample. + Any subgraph of a complete graph is also complete. + Any #emph[induced] subgraph of a complete graph is also complete. + Any subgraph of a bipartite graph is bipartite. + Any subgraph of a tree is a tree. #solutionbox[ + False. + True. + True. + False. ] Let #math.equation(block: false, alt: "k sub 1 , k sub 2 , and so on , k sub j")[$k_(1) , k_(2) , … , k_(j)$] be a list of positive integers that sum to #math.equation(block: false, alt: "n")[$n$] (i.e., #math.equation(block: false, alt: "∑ i equals 1 j k sub i equals n")[$limits(∑)^(j)_(i = 1) k_(i) = n$]). Use two graphs containing #math.equation(block: false, alt: "n")[$n$] vertices to explain why #math.equation(block: true, alt: "∑ i equals 1 j open parenthesis the fraction k sub i over 2 close parenthesis less than or equal to open parenthesis the fraction n over 2 close parenthesis")[$limits(∑)^(j)_(i = 1) ( binom(k_(i), 2) ) ≤ ( binom(n, 2) )$] . How many edges does #math.equation(block: false, alt: "K sub n")[$K_(n)$] have? One of the two graphs will not be connected (unless #math.equation(block: false, alt: "j equals 1")[$j = 1$]). We often define graph theory concepts using set theory. For example, given a graph #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$] and a vertex #math.equation(block: false, alt: "v ∈ V")[$v ∈ V$], we define #math.equation(block: true, alt: "N open parenthesis v close parenthesis equals open brace u ∈ V : open brace v , u close brace ∈ E close brace")[$N ( v ) = \{ u ∈ V : \{ v , u \} ∈ E \}$] . We define #math.equation(block: false, alt: "N open bracket v close bracket equals N open parenthesis v close parenthesis union open brace v close brace")[$N [ v ] = N ( v ) ∪ \{ v \}$]. The goal of this problem is to figure out what all this means. + Let #math.equation(block: false, alt: "G")[$G$] be the graph with #math.equation(block: false, alt: "V equals open brace a , b , c , d , e , f close brace")[$V = \{ a , b , c , d , e , f \}$] and #math.equation(block: false, alt: "E equals open brace open brace a , b close brace , open brace a , e close brace , open brace b , c close brace , open brace b , e close brace , open brace c , d close brace , open brace c , f close brace , open brace d , f close brace , open brace e , f close brace close brace")[$E = \{ \{ a , b \} , \{ a , e \} , \{ b , c \} , \{ b , e \} , \{ c , d \} , \{ c , f \} , \{ d , f \} , \{ e , f \} \}$]. Find #math.equation(block: false, alt: "N open parenthesis a close parenthesis")[$N ( a )$], #math.equation(block: false, alt: "N open bracket a close bracket")[$N [ a ]$], #math.equation(block: false, alt: "N open parenthesis c close parenthesis")[$N ( c )$], and #math.equation(block: false, alt: "N open bracket c close bracket")[$N [ c ]$]. + What is the largest and smallest possible values for #math.equation(block: false, alt: "vertical bar N open parenthesis v close parenthesis vertical bar")[$| N ( v ) |$] and #math.equation(block: false, alt: "vertical bar N open bracket v close bracket vertical bar")[$| N [ v ] |$] for the graph in part (a)? Explain. + Give an example of a graph #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$] (probably different than the one above) for which #math.equation(block: false, alt: "N open bracket v close bracket equals V")[$N [ v ] = V$] for some vertex #math.equation(block: false, alt: "v ∈ V")[$v ∈ V$]. Is there a graph for which #math.equation(block: false, alt: "N open bracket v close bracket equals V")[$N [ v ] = V$] for #emph[all] #math.equation(block: false, alt: "v ∈ V")[$v ∈ V$]? Explain. + Give an example of a graph #math.equation(block: false, alt: "G equals open parenthesis V , E close parenthesis")[$G = ( V , E )$] for which #math.equation(block: false, alt: "N open parenthesis v close parenthesis equals ∅")[$N ( v ) = upright(∅)$] for some #math.equation(block: false, alt: "v ∈ V")[$v ∈ V$]. Is there an example of such a graph for which #math.equation(block: false, alt: "N open bracket u close bracket equals V")[$N [ u ] = V$] for some other #math.equation(block: false, alt: "u ∈ V")[$u ∈ V$] as well? Explain. + Describe in words what #math.equation(block: false, alt: "N open parenthesis v close parenthesis")[$N ( v )$] and #math.equation(block: false, alt: "N open bracket v close bracket")[$N [ v ]$] mean in general. You should be able to deduce everything directly from the definition. However, perhaps it would be helpful to know that the #math.equation(block: false, alt: "N")[$N$] stands for #strong[neighborhood]. A graph is a way of representing the relationships between elements in a set: an edge between the vertices #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] tells us that #math.equation(block: false, alt: "x")[$x$] is related to #math.equation(block: false, alt: "y")[$y$] (which we can write as #math.equation(block: false, alt: "x ∼ y")[$x ∼ y$]). Not all sorts of relationships can be represented by a graph though. For each relationship described below, either draw the graph or explain why the relationship cannot be represented by a graph. + The set #math.equation(block: false, alt: "V equals open brace 1 , 2 , and so on , 9 close brace")[$V = \{ 1 , 2 , … , 9 \}$] and the relationship #math.equation(block: false, alt: "x ∼ y")[$x ∼ y$] when #math.equation(block: false, alt: "x minus y")[$x − y$] is a non-zero multiple of 3. + The set #math.equation(block: false, alt: "V equals open brace 1 , 2 , and so on , 9 close brace")[$V = \{ 1 , 2 , … , 9 \}$] and the relationship #math.equation(block: false, alt: "x ∼ y")[$x ∼ y$] when #math.equation(block: false, alt: "y")[$y$] is a multiple of #math.equation(block: false, alt: "x")[$x$]. + The set #math.equation(block: false, alt: "V equals open brace 1 , 2 , and so on , 9 close brace")[$V = \{ 1 , 2 , … , 9 \}$] and the relationship #math.equation(block: false, alt: "x ∼ y")[$x ∼ y$] when #math.equation(block: false, alt: "0 less than vertical bar x minus y vertical bar less than 3")[$0 < | x − y | < 3$]. Be careful to make sure the edges are not “directed.” In a graph, if #math.equation(block: false, alt: "a")[$a$] is adjacent to #math.equation(block: false, alt: "b")[$b$], then #math.equation(block: false, alt: "b")[$b$] is adjacent to #math.equation(block: false, alt: "a")[$a$]. In the language of relations, we say that the edge relation is #strong[symmetric]. Consider graphs with #math.equation(block: false, alt: "n")[$n$] vertices. Remember, graphs do not need to be #emph[connected]. + How many edges must the graph have to guarantee at least one vertex has degree two or more? Prove your answer. + How many edges must the graph have to guarantee all vertices have degree two or more? Prove your answer. You might want to answer the questions for some specific values of #math.equation(block: false, alt: "n")[$n$] to get a feel for them, but your final answers should be in terms of #math.equation(block: false, alt: "n")[$n$]. Prove that any graph with at least two vertices must have two vertices of the same degree. Try a small example first: any graph with 8 vertices must have two vertices of the same degree. If not, what would the degree sequence be? Suppose #math.equation(block: false, alt: "G")[$G$] is a connected graph with #math.equation(block: false, alt: "n greater than 1")[$n > 1$] vertices and #math.equation(block: false, alt: "n minus 1")[$n − 1$] edges. Prove that #math.equation(block: false, alt: "G")[$G$] has a vertex of degree 1. Use the handshake lemma. What would happen if all the vertices had degree 2?