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

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

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

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

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

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

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

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

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


    
== 5.3#h(0.6em)Planar Graphs


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
When a connected graph can be drawn without any edges crossing,
        it is called #strong[planar].
        When a planar graph is drawn in this way,
        it divides the plane into regions called #strong[faces].


      + Draw, if possible,
              two different planar graphs with the same number of vertices, edges,
              and faces.
+ Draw, if possible,
              two different planar graphs with the same number of vertices and edges,
              but a different number of faces.
]


    When is it possible to draw a graph so that none of the edges cross?
      If this #emph[is] possible,
      we say the graph is #strong[planar]
      (since you can draw it on the #emph[plane]).


    Notice that the definition of planar includes the phrase
      “it is possible to.”
      This means that even if a graph does not look like it is planar,
      it still might be.
      Perhaps you can redraw it in a way in which no edges cross.
      For example, this is a planar graph:


    #figure(figph[A drawing of K2,3 with two vertices in a top row, each adjacent to each of the three vertices on the bottom row.], alt: "A drawing of K2,3 with two vertices in a top row, each adjacent to each of the three vertices on the bottom row.", caption: none)


    That is because we can redraw it like this:


    #figure(figph[Another drawing of K2,3. A single vertex on a top row is adjacent to three vertices in a row below it. Each of these vertices are adjacent to a single vertex below (and to the right of) them.], alt: "Another drawing of K2,3. A single vertex on a top row is adjacent to three vertices in a row below it. Each of these vertices are adjacent to a single vertex below (and to the right of) them.", caption: none)


    The graphs are the same, so if one is planar, the other must be too.
      However, the original drawing of the graph was not a
      #strong[planar representation] of the graph.


    When a planar graph is drawn without edges crossing,
      the edges and vertices of the graph divide the plane into regions.
      We will call each region a #strong[face].
      The graph above has 3 faces
      (yes, we #emph[do] include the
      “outside” region as a face).
      The number of faces does not change no matter how you draw the graph
      (as long as you do so without the edges crossing),
      so it makes sense to ascribe the number of faces as a property of the planar graph.


    WARNING: you can only count faces when the graph is drawn in a planar way.
      For example,
      consider these two representations of the same graph:


    #figure(figph[A drawing of K4 with four vertices in a square and edges forming the sides of the square plus two more crossing through the center.], alt: "A drawing of K4 with four vertices in a square and edges forming the sides of the square plus two more crossing through the center.", caption: none)


    #figure(figph[A drawing of K4 with four vertices arranged in a square and edges forming the sides of the square. Another edge crosses from the bottom left to the top right corners. A curved edge loops outside of the square from the top left to bottom right vertices. No edges intersect.], alt: "A drawing of K4 with four vertices arranged in a square and edges forming the sides of the square. Another edge crosses from the bottom left to the top right corners. A curved edge loops outside of the square from the top left to bottom right vertices. No edges intersect.", caption: none)


    If you try to count faces using the graph on the left,
      you might say there are 5 faces
      (including the outside).
      But drawing the graph with a planar representation shows that in fact there are only 4 faces.


    There is a connection between the number of vertices (#math.equation(block: false, alt: "v")[$v$]),
      the number of edges (#math.equation(block: false, alt: "e")[$e$]) and the number of faces (#math.equation(block: false, alt: "f")[$f$]) in any connected planar graph.
      This relationship is called Euler's formula.


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Euler's Formula for Planar Graphs]


      For any connected planar graph with #math.equation(block: false, alt: "v")[$v$] vertices,
        #math.equation(block: false, alt: "e")[$e$] edges and #math.equation(block: false, alt: "f")[$f$] faces, we have


      #math.equation(block: true, alt: "v minus e plus f equals 2")[$v − e + f = 2$]
      .
]


    Why is Euler's formula true?
      One way to convince yourself of its validity is to draw a planar graph step by step.
      Start with the graph #math.equation(block: false, alt: "P sub 2")[$P_(2)$]:


    #figure(figph[Two vertices connected by an edge.], alt: "Two vertices connected by an edge.", caption: none)


    Any connected graph
      (besides just a single isolated vertex)
      must contain this subgraph.
      Now build up to your graph by adding edges and vertices.
      Each step will consist of either adding a new vertex connected by a new edge to part of your graph
      (so creating a new “spike”)
      or by connecting two vertices already in the graph with a new edge
      (completing a circuit).


    #figure(figph[A graph with four vertices arranged in a square. The top left vertex is adjacent to the other three vertices, and the top right and bottom right vertices are also adjacent. A dashed edge leads from the top right vertex of the square to a fifth vertex below and to its right.], alt: "A graph with four vertices arranged in a square. The top left vertex is adjacent to the other three vertices, and the top right and bottom right vertices are also adjacent. A dashed edge leads from the top right vertex of the square to a fifth vertex below and to its right.", caption: none)


    #figure(figph[A graph with four vertices arranged in a square. The top left vertex is adjacent to the other three vertices, and the top right and bottom right vertices are also adjacent. A dashed edge connects the bottom two vertices.], alt: "A graph with four vertices arranged in a square. The top left vertex is adjacent to the other three vertices, and the top right and bottom right vertices are also adjacent. A dashed edge connects the bottom two vertices.", caption: none)


    What do these “moves” do?
      When adding the spike,
      the number of edges increases by 1, the number of vertices increases by one,
      and the number of faces remains the same.
      But this means that #math.equation(block: false, alt: "v minus e plus f")[$v − e + f$] does not change.
      Completing a circuit adds one edge,
      adds one face, and keeps the number of vertices the same.
      So again, #math.equation(block: false, alt: "v minus e plus f")[$v − e + f$] does not change.


    Since we can build any graph using a combination of these two moves,
      and doing so never changes the quantity #math.equation(block: false, alt: "v minus e plus f")[$v − e + f$],
      that quantity will be the same for all graphs.
      But notice that our starting graph #math.equation(block: false, alt: "P sub 2")[$P_(2)$] has #math.equation(block: false, alt: "v equals 2")[$v = 2$],
      #math.equation(block: false, alt: "e equals 1")[$e = 1$] and #math.equation(block: false, alt: "f equals 1")[$f = 1$], so #math.equation(block: false, alt: "v minus e plus f equals 2")[$v − e + f = 2$].
      This argument is essentially a proof by induction.
      A good exercise would be to rewrite it as a formal induction proof.


    
      
=== Non-planar Graphs


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
For the complete graphs #math.equation(block: false, alt: "K sub n")[$K_(n)$],
        we would like to be able to say something about the number of vertices,
        edges, and
        (if the graph is planar)
        faces.
        Let's first consider #math.equation(block: false, alt: "K sub 3")[$K_(3)$]:


        + How many vertices does #math.equation(block: false, alt: "K sub 3")[$K_(3)$] have?
              How many edges?
+ If #math.equation(block: false, alt: "K sub 3")[$K_(3)$] is planar, how many faces should it have?


        Repeat parts (1) and (2) for #math.equation(block: false, alt: "K sub 4")[$K_(4)$],
        #math.equation(block: false, alt: "K sub 5")[$K_(5)$], and #math.equation(block: false, alt: "K sub 23")[$K_(23)$].


        What about complete bipartite graphs?
        How many vertices, edges, and faces
        (if it were planar)
        does #math.equation(block: false, alt: "K sub 7 , 4")[$K_(7 , 4)$] have?
        For which values of #math.equation(block: false, alt: "m")[$m$] and #math.equation(block: false, alt: "n")[$n$] are #math.equation(block: false, alt: "K sub n")[$K_(n)$] and #math.equation(block: false, alt: "K sub m , n")[$K_(m , n)$] planar?
]


      Not all graphs are planar.
      If there are too many edges and too few vertices,
      then some of the edges will need to intersect.
      The smallest graph where this happens is #math.equation(block: false, alt: "K sub 5")[$K_(5)$].


      #figure(figph[A copy of K5: five vertices arranged in a pentagon with edges connecting every vertex to every other vertex.], alt: "A copy of K5: five vertices arranged in a pentagon with edges connecting every vertex to every other vertex.", caption: none)


      If you try to redraw this without edges crossing,
      you quickly get into trouble.
      There seems to be one edge too many.
      In fact, we can prove that no matter how you draw it,
      #math.equation(block: false, alt: "K sub 5")[$K_(5)$] will always have edges crossing.


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#math.equation(block: false, alt: "K sub 5")[$K_(5)$] is not planar.
]


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
The proof is by contradiction.
        So assume that #math.equation(block: false, alt: "K sub 5")[$K_(5)$] is planar.
        Then the graph must satisfy Euler's formula for planar graphs. #math.equation(block: false, alt: "K sub 5")[$K_(5)$] has 5 vertices and 10 edges,
        so we get


        #math.equation(block: true, alt: "5 minus 10 plus f equals 2")[$5 − 10 + f = 2$]
        ,
        which says that if the graph is drawn without any edges crossing,
        there would be #math.equation(block: false, alt: "f equals 7")[$f = 7$] faces.


        Now consider how many edges surround each face.
        Each face must be surrounded by at least 3 edges.
        Let #math.equation(block: false, alt: "B")[$B$] be the total number of #emph[boundaries]
        around all the faces in the graph.
        Thus we have that #math.equation(block: false, alt: "3 f less than or equal to B")[$3 f ≤ B$].
        But also #math.equation(block: false, alt: "B equals 2 e")[$B = 2 e$],
        since each edge is used as a boundary exactly twice.
        Putting this together we get


        #math.equation(block: true, alt: "3 f less than or equal to 2 e")[$3 f ≤ 2 e$]
        .


        But this is impossible,
        since we have already determined that #math.equation(block: false, alt: "f equals 7")[$f = 7$] and #math.equation(block: false, alt: "e equals 10")[$e = 10$],
        and #math.equation(block: false, alt: "21 ≰ 20")[$21 ≰ 20$].
        This is a contradiction so in fact #math.equation(block: false, alt: "K sub 5")[$K_(5)$] is not planar.
]


      The other simplest graph which is not planar is #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$]


      #figure(figph[A drawing of K3,3 with a row of three vertices on top, each adjacent to the three vertices in a row directly below.], alt: "A drawing of K3,3 with a row of three vertices on top, each adjacent to the three vertices in a row directly below.", caption: none)


      Proving that #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] is not planar answers the houses and utilities puzzle:
      it is not possible to connect each of three houses to each of three utilities without the lines crossing.


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] is not planar.
]


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Again, we proceed by contradiction.
        Suppose #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] were planar.
        Then by Euler's formula there will be 5 faces,
        since #math.equation(block: false, alt: "v equals 6")[$v = 6$], #math.equation(block: false, alt: "e equals 9")[$e = 9$], and #math.equation(block: false, alt: "6 minus 9 plus f equals 2")[$6 − 9 + f = 2$].


        How many boundaries surround these 5 faces?
        Let #math.equation(block: false, alt: "B")[$B$] be this number.
        Since each edge is used as a boundary twice, we have #math.equation(block: false, alt: "B equals 2 e")[$B = 2 e$].
        Also, #math.equation(block: false, alt: "B greater than or equal to 4 f")[$B ≥ 4 f$] since each face is surrounded by 4 or more boundaries.
        We know this is true because #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] is bipartite,
        so does not contain any 3-edge cycles.
        Thus


        #math.equation(block: true, alt: "4 f less than or equal to 2 e")[$4 f ≤ 2 e$]
        .


        But this would say that #math.equation(block: false, alt: "20 less than or equal to 18")[$20 ≤ 18$], which is clearly false.
        Thus #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] is not planar.
]


      Note the similarities and differences in these proofs.
      Both are proofs by contradiction,
      and both start with using Euler's formula to derive the (supposed) number of faces in the graph.
      Then we find a relationship between the number of faces and the number of edges based on how many edges surround each face.
      This is the only difference.
      In the proof for #math.equation(block: false, alt: "K sub 5")[$K_(5)$],
      we got #math.equation(block: false, alt: "3 f less than or equal to 2 e")[$3 f ≤ 2 e$] and for #math.equation(block: false, alt: "K sub 3 , 3")[$K_(3 , 3)$] we go #math.equation(block: false, alt: "4 f less than or equal to 2 e")[$4 f ≤ 2 e$].
      The coefficient of #math.equation(block: false, alt: "f")[$f$] is the key.
      It is the smallest number of edges which could surround any face.
      If some number of edges surround a face,
      then these edges form a cycle.
      So that number is the size of the smallest cycle in the graph.


      In general, if we let #math.equation(block: false, alt: "g")[$g$] be the size of the smallest cycle in a graph (#math.equation(block: false, alt: "g")[$g$] stands for #emph[girth],
      which is the technical term for this) then for any planar graph we have #math.equation(block: false, alt: "g f less than or equal to 2 e")[$g f ≤ 2 e$].
      When this disagrees with Euler's formula,
      we know for sure that the graph cannot be planar.


    
    
      
=== Polyhedra


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
A cube
            
        is an example of a convex polyhedron.
        It contains 6 identical squares for its faces, 8 vertices,
        and 12 edges.
        The cube is a #strong[regular polyhedron]
        (also known as a #strong[Platonic solid])
        because each face is an identical regular polygon and each vertex joins an equal number of faces.


        There are exactly four other regular polyhedra:
        the tetrahedron, octahedron, dodecahedron,
        and icosahedron with 4, 8, 12 and 20 faces respectively.
        How many vertices and edges do each of these have?
]


      Another area of mathematics where you might have heard the terms
      “vertex,” “edge,”
      and “face” is geometry.
      A #strong[polyhedron]
      is a geometric solid made up of flat polygonal faces joined at edges and vertices.
      We are especially interested in #strong[convex]
      polyhedra, which means that any line segment connecting two points on the interior of the polyhedron must be entirely contained inside the polyhedron.
      An alternative definition for convex is that the internal angle formed by any two faces must be less than #math.equation(block: false, alt: "180 deg")[$180 deg$].


      Notice that since #math.equation(block: false, alt: "8 minus 12 plus 6 equals 2")[$8 − 12 + 6 = 2$], the vertices,
      edges and faces of a cube satisfy Euler's formula for planar graphs.
      This is not a coincidence.
      We can represent a cube as a planar graph by projecting the vertices and edges onto the plane.
      One such projection looks like this:


      #figure(figph[Eight vertices arranged as a smaller square inside a larger square. Edges from the perimeters of both squares, and edges connect each vertex of the small square to its closest vertex of the larger square.], alt: "Eight vertices arranged as a smaller square inside a larger square. Edges from the perimeters of both squares, and edges connect each vertex of the small square to its closest vertex of the larger square.", caption: none)


      In fact, #emph[every] convex polyhedron can be projected onto the plane without edges crossing.
      Think of placing the polyhedron inside a sphere,
      with a light at the center of the sphere.
      The edges and vertices of the polyhedron cast a shadow onto the interior of the sphere.
      You can then cut a hole in the sphere in the middle of one of the projected faces and “stretch”
      the sphere to lie down flat on the plane.
      The face that was punctured becomes the
      “outside” face of the planar graph.


      The point is, we can apply what we know about graphs
      (in particular planar graphs)
      to convex polyhedra.
      Since every convex polyhedron can be represented as a planar graph,
      we see that Euler's formula for planar graphs holds for all convex polyhedra as well.
      We also can apply the same sort of reasoning we use for graphs in other contexts to convex polyhedra.
      For example,
      we know that there is no convex polyhedron with 11 vertices all of degree 3, as this would make 33/2 edges.


      #examplebox("Example 1")[][
Is there a convex polyhedron consisting of three triangles and six pentagons?
          What about three triangles,
          six pentagons and five heptagons (7-sided polygons)?


        
        #solutionbox[
How many edges would such polyhedra have?
          For the first proposed polyhedron,
          the triangles would contribute a total of 9 edges,
          and the pentagons would contribute 30.
          However, this counts each edge twice
          (as each edge borders exactly two faces),
          giving 39/2 edges, an impossibility.
          There is no such polyhedron.


          The second polyhedron does not have this obstacle.
          The extra 35 edges contributed by the heptagons give a total of 74/2 = 37 edges.
          So far so good.
          Now how many vertices does this supposed polyhedron have?
          We can use Euler's formula.
          There are 14 faces, so we have
          #math.equation(block: false, alt: "v minus 37 plus 14 equals 2")[$v − 37 + 14 = 2$] or equivalently #math.equation(block: false, alt: "v equals 25")[$v = 25$].
          But now use the vertices to count the edges again.
          Each vertex must have degree #emph[at least] three
          (that is, each vertex joins at least three faces since the interior angle of all the polygons must be less that #math.equation(block: false, alt: "180 degrees")[$180^(∘)$]),
          so the sum of the degrees of vertices is at least 75.
          Since the sum of the degrees must be exactly twice the number of edges,
          this says that there are strictly more than 37 edges.
          Again, there is no such polyhedron.
]
]


      To conclude this application of planar graphs,
      consider the regular polyhedra.
      We claimed there are only five.
      How do we know this is true?
      We can prove it using graph theory.


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
There are exactly five regular polyhedra.
]


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Recall that all the faces of a regular polyhedron are identical regular polygons,
        and that each vertex has the same degree.
        Consider four cases, depending on the type of regular polygon.


        #strong[Case 1]: Each face is a triangle.
        Let #math.equation(block: false, alt: "f")[$f$] be the number of faces.
        There are then #math.equation(block: false, alt: "3 f / 2")[$3 f / 2$] edges.
        Using Euler's formula we have
        #math.equation(block: false, alt: "v minus 3 f / 2 plus f equals 2")[$v − 3 f / 2 + f = 2$] so #math.equation(block: false, alt: "v equals 2 plus f / 2")[$v = 2 + f / 2$].
        Now each vertex has the same degree, say #math.equation(block: false, alt: "k")[$k$].
        So the number of edges is also #math.equation(block: false, alt: "k v / 2")[$k v / 2$].
        Putting this together gives


        #math.equation(block: true, alt: "e equals the fraction 3 f over 2 equals the fraction k open parenthesis 2 plus f / 2 close parenthesis over 2")[$e = frac(3 f, 2) = frac(k ( 2 + f / 2 ), 2)$]
        ,
        which says


        #math.equation(block: true, alt: "k equals the fraction 6 f over 4 plus f")[$k = frac(6 f, 4 + f)$]
        .


        Both #math.equation(block: false, alt: "k")[$k$] and #math.equation(block: false, alt: "f")[$f$] must be positive integers.
        Note that #math.equation(block: false, alt: "the fraction 6 f over 4 plus f")[$frac(6 f, 4 + f)$] is an increasing function for positive #math.equation(block: false, alt: "f")[$f$],
        bounded above by a horizontal asymptote at #math.equation(block: false, alt: "k equals 6")[$k = 6$].
        Thus the only possible values for #math.equation(block: false, alt: "k")[$k$] are 3, 4, and 5.
        Each of these are possible.
        To get #math.equation(block: false, alt: "k equals 3")[$k = 3$], we need #math.equation(block: false, alt: "f equals 4")[$f = 4$]
        (this is the tetrahedron).
            
        For #math.equation(block: false, alt: "k equals 4")[$k = 4$] we take #math.equation(block: false, alt: "f equals 8")[$f = 8$]
        (the octahedron).
            
        For #math.equation(block: false, alt: "k equals 5")[$k = 5$] take #math.equation(block: false, alt: "f equals 20")[$f = 20$]
        (the icosahedron).
            
        Thus there are exactly three regular polyhedra with triangles for faces.


        #strong[Case 2]: Each face is a square.
        Now we have #math.equation(block: false, alt: "e equals 4 f / 2 equals 2 f")[$e = 4 f / 2 = 2 f$].
        Using Euler's formula we get #math.equation(block: false, alt: "v equals 2 plus f")[$v = 2 + f$],
        and counting edges using the degree #math.equation(block: false, alt: "k")[$k$] of each vertex gives us


        #math.equation(block: true, alt: "e equals 2 f equals the fraction k open parenthesis 2 plus f close parenthesis over 2")[$e = 2 f = frac(k ( 2 + f ), 2)$]
        .


        Solving for #math.equation(block: false, alt: "k")[$k$] gives


        #math.equation(block: true, alt: "k equals the fraction 4 f over 2 plus f equals the fraction 8 f over 4 plus 2 f")[$k = frac(4 f, 2 + f) = frac(8 f, 4 + 2 f)$]
        .


        This is again an increasing function,
        but this time the horizontal asymptote is at #math.equation(block: false, alt: "k equals 4")[$k = 4$],
        so the only possible value that #math.equation(block: false, alt: "k")[$k$] could take is 3.
        This produces 6 faces, and we have a cube.
        There is only one regular polyhedron with square faces.


        #strong[Case 3]: Each face is a pentagon.
        We perform the same calculation as above,
        this time getting #math.equation(block: false, alt: "e equals 5 f / 2")[$e = 5 f / 2$] so #math.equation(block: false, alt: "v equals 2 plus 3 f / 2")[$v = 2 + 3 f / 2$].
        Then


        #math.equation(block: true, alt: "e equals the fraction 5 f over 2 equals the fraction k open parenthesis 2 plus 3 f / 2 close parenthesis over 2")[$e = frac(5 f, 2) = frac(k ( 2 + 3 f / 2 ), 2)$]
        ,
        so


        #math.equation(block: true, alt: "k equals the fraction 10 f over 4 plus 3 f")[$k = frac(10 f, 4 + 3 f)$]
        .


        Now the horizontal asymptote is at #math.equation(block: false, alt: "the fraction 10 over 3")[$frac(10, 3)$].
        This is less than 4, so we can only hope of making #math.equation(block: false, alt: "k equals 3")[$k = 3$].
        We can do so by using 12 pentagons, getting the dodecahedron.
            
        This is the only regular polyhedron with pentagons as faces.


        #strong[Case 4]: Each face is an #math.equation(block: false, alt: "n")[$n$]-gon with #math.equation(block: false, alt: "n greater than or equal to 6")[$n ≥ 6$].
        Following the same procedure as above, we deduce that


        #math.equation(block: true, alt: "k equals the fraction 2 n f over 4 plus open parenthesis n minus 2 close parenthesis f")[$k = frac(2 n f, 4 + ( n − 2 ) f)$]
        ,
        which will be increasing to a horizontal asymptote of #math.equation(block: false, alt: "the fraction 2 n over n minus 2")[$frac(2 n, n − 2)$].
        When #math.equation(block: false, alt: "n equals 6")[$n = 6$], this asymptote is at #math.equation(block: false, alt: "k equals 3")[$k = 3$].
        Any larger value of #math.equation(block: false, alt: "n")[$n$] will give an even smaller asymptote.
        Therefore no regular polyhedra exist with faces larger than pentagons.
        Notice that you can tile the plane with hexagons.
        This is an infinite planar graph;
        each vertex has degree 3.
        These infinitely many hexagons correspond to the limit as
        #math.equation(block: false, alt: "f → ∞")[$f → upright(∞)$] to make #math.equation(block: false, alt: "k equals 3")[$k = 3$].
]


    
    
      
        Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces?
        Explain.


        #solutionbox[
No.
        A (connected) planar graph must satisfy Euler's formula:
        #math.equation(block: false, alt: "v minus e plus f equals 2")[$v − e + f = 2$].
        Here #math.equation(block: false, alt: "v minus e plus f equals 6 minus 10 plus 5 equals 1")[$v − e + f = 6 − 10 + 5 = 1$].
]


      
      
        The graph #math.equation(block: false, alt: "G")[$G$] has 6 vertices with degrees #math.equation(block: false, alt: "2 , 2 , 3 , 4 , 4 , 5")[$2 , 2 , 3 , 4 , 4 , 5$].
        How many edges does #math.equation(block: false, alt: "G")[$G$] have?
        Could #math.equation(block: false, alt: "G")[$G$] be planar?
        If so, how many faces would it have.
        If not, explain.


        #solutionbox[
#math.equation(block: false, alt: "G")[$G$] has 10 edges, since #math.equation(block: false, alt: "10 equals the fraction 2 plus 2 plus 3 plus 4 plus 4 plus 5 over 2")[$10 = frac(2 + 2 + 3 + 4 + 4 + 5, 2)$].
        It could be planar,
        and then it would have 6 faces, using Euler's formula:
        #math.equation(block: false, alt: "6 minus 10 plus f equals 2")[$6 − 10 + f = 2$] means #math.equation(block: false, alt: "f equals 6")[$f = 6$].
        To make sure that it is actually planar though,
        we would need to draw a graph with those vertex degrees without edges crossing.
        This can be done by trial and error
        (and is possible).
]


      
      
        Is it possible for a connected graph with 7 vertices and 10 edges to be drawn so that no edges cross and create 4 faces?  Explain.


        
          What would Euler's formula tell you?


        
      
      
        Is it possible for a graph with 10 vertices and edges to be a connected planar graph?  Explain.


      
      
        Is there a connected planar graph with an odd number of faces where every vertex has degree 6?  Prove your answer.


        
          You can use the handshake lemma to find the number of edges, in terms of #math.equation(block: false, alt: "v")[$v$], the number of vertices.


        
      
      
        I'm thinking of a polyhedron containing 12 faces.
        Seven are triangles and four are quadralaterals.
        The polyhedron has 11 vertices including those around the mystery face.
        How many sides does the last face have?


        #solutionbox[
Say the last polyhedron has #math.equation(block: false, alt: "n")[$n$] edges,
        and also #math.equation(block: false, alt: "n")[$n$] vertices.
        The total number of edges the polyhedron has then is #math.equation(block: false, alt: "open parenthesis 7 times 3 plus 4 times 4 plus n close parenthesis / 2 equals open parenthesis 37 plus n close parenthesis / 2")[$( 7 ⋅ 3 + 4 ⋅ 4 + n ) / 2 = ( 37 + n ) / 2$].
        In particular,
        we know the last face must have an odd number of edges.
        We also have that #math.equation(block: false, alt: "v equals 11")[$v = 11$].
        By Euler's formula, we have #math.equation(block: false, alt: "11 minus open parenthesis 37 plus n close parenthesis / 2 plus 12 equals 2")[$11 − ( 37 + n ) / 2 + 12 = 2$],
        and solving for #math.equation(block: false, alt: "n")[$n$] we get #math.equation(block: false, alt: "n equals 5")[$n = 5$],
        so the last face is a pentagon.
]


      
      
        Consider some classic polyhedrons.


        + An #emph[octahedron] is a regular polyhedron made up of 8 equilateral triangles
              (it sort of looks like two pyramids with their bases glued together).
              Draw a planar graph representation of an octahedron.
              How many vertices, edges and faces does an octahedron
              (and your graph)
              have?
+ The traditional design of a soccer ball is in fact a
              (spherical projection of a)
              truncated icosahedron.
              This consists of 12 regular pentagons and 20 regular hexagons.
              No two pentagons are adjacent
              (so the edges of each pentagon are shared only by hexagons).
              How many vertices,
              edges, and faces does a truncated icosahedron have?
              Explain how you arrived at your answers.
              Bonus: draw the planar graph representation of the truncated icosahedron.
+ Your “friend” claims that he has constructed a convex polyhedron out of 2 triangles, 2 squares, 6 pentagons and 5 octagons.
              Prove that your friend is lying.
              Hint: each vertex of a convex polyhedron must border at least three faces.


      
      
        Prove Euler's formula using induction on the number of edges in the graph.


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement,
          “every connected planar graph containing #math.equation(block: false, alt: "n")[$n$] edges satisfies #math.equation(block: false, alt: "v minus n plus f equals 2")[$v − n + f = 2$].”
          We will show #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$].


            Base case: there is only one graph with zero edges, namely a single isolated vertex. In this case #math.equation(block: false, alt: "v equals 1")[$v = 1$], #math.equation(block: false, alt: "f equals 1")[$f = 1$] and #math.equation(block: false, alt: "e equals 0")[$e = 0$], so Euler's formula holds.


            Inductive case: Suppose #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for some arbitrary #math.equation(block: false, alt: "k greater than or equal to 0")[$k ≥ 0$]. Now consider an arbitrary graph containing #math.equation(block: false, alt: "k plus 1")[$k + 1$] edges (and #math.equation(block: false, alt: "v")[$v$] vertices and #math.equation(block: false, alt: "f")[$f$] faces). No matter what this graph looks like, we can remove a single edge to get a graph with #math.equation(block: false, alt: "k")[$k$] edges which we can apply the inductive hypothesis to.


            There are two cases: either the graph contains a cycle or it does not. If the graph contains a cycle, then pick an edge that is part of this cycle, and remove it.  This will not disconnect the graph, and will decrease the number of faces by 1 (since the edge was bordering two distinct faces).  So by the inductive hypothesis we will have #math.equation(block: false, alt: "v minus k plus f minus 1 equals 2")[$v − k + f − 1 = 2$]. Adding the edge back will give #math.equation(block: false, alt: "v minus open parenthesis k plus 1 close parenthesis plus f equals 2")[$v − ( k + 1 ) + f = 2$] as needed.


            If the graph does not contain a cycle, then it is a tree, so has a vertex of degree 1.  Then we can pick the edge to remove to be incident to such a degree 1 vertex. In this case, also remove that vertex. The smaller graph will now satisfy #math.equation(block: false, alt: "v minus 1 minus k plus f equals 2")[$v − 1 − k + f = 2$] by the induction hypothesis (removing the edge and vertex did not reduce the number of faces). Adding the edge and vertex back gives #math.equation(block: false, alt: "v minus open parenthesis k plus 1 close parenthesis plus f equals 2")[$v − ( k + 1 ) + f = 2$], as required.


            Therefore, by the principle of mathematical induction, Euler's formula holds for all planar graphs.
]
]


      
      
        Prove Euler's formula using induction on the number of
        #emph[vertices] in the graph.


      
      
        Euler's formula (#math.equation(block: false, alt: "v minus e plus f equals 2")[$v − e + f = 2$]) holds for all
        #emph[connected] planar graphs.
        What if a graph is not connected?
        Suppose a planar graph has two components.
        What is the value of #math.equation(block: false, alt: "v minus e plus f")[$v − e + f$] now?
        What if it has #math.equation(block: false, alt: "k")[$k$] components?


      
      
        Prove that the #strong[Petersen graph]
        (below) is not planar.


        #figure(figph[A drawing of the Petersen graph: ten vertices arranged as a larger pentagon around a smaller pentagram (five pointed star). Edges form the outside of the larger pentagon and the crossing lines of the pentagram. Each vertex of the larger pentagon is adjacent to the closest vertex of the inside pentagram.], alt: "A drawing of the Petersen graph: ten vertices arranged as a larger pentagon around a smaller pentagram (five pointed star). Edges form the outside of the larger pentagon and the crossing lines of the pentagram. Each vertex of the larger pentagon is adjacent to the closest vertex of the inside pentagram.", caption: none)


        
          What is the length of the shortest cycle? (This quantity is usually called the
        #strong[girth] of the graph.)


        
      
      
        Prove that any planar graph with #math.equation(block: false, alt: "v")[$v$] vertices and #math.equation(block: false, alt: "e")[$e$] edges satisfies #math.equation(block: false, alt: "e less than or equal to 3 v minus 6")[$e ≤ 3 v − 6$].


        #solutionbox[
#notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
We know in any planar graph the number of faces #math.equation(block: false, alt: "f")[$f$] satisfies
          #math.equation(block: false, alt: "3 f less than or equal to 2 e")[$3 f ≤ 2 e$] since each face is bounded by at least three edges,
          but each edge borders two faces.
          Combine this with Euler's formula:


            #math.equation(block: true, alt: "v minus e plus f equals 2")[$v − e + f = 2$]
            #math.equation(block: true, alt: "v minus e plus the fraction 2 e over 3 greater than or equal to 2")[$v − e + frac(2 e, 3) ≥ 2$]
            #math.equation(block: true, alt: "3 v minus e greater than or equal to 6")[$3 v − e ≥ 6$]
            #math.equation(block: true, alt: "3 v minus 6 greater than or equal to e")[$3 v − 6 ≥ e$]
            .
]
]


      
      
        Prove that any planar graph must have a vertex of degree 5 or less.


      
      
        Give a careful proof that the graph below is not planar.


        #figure(figph[A graph with 11 vertices. A single vertex in the center, then five vertices equally spaced around a ring around it, and five more equally spaced around a ring around those. Edges form the sides of a pentagon for the outer ring of vertices. Each outer vertex is also adjacent to two inner vertices: the two on either side of the vertex closest to it. Finally, every inner vertex is also adjacent to the center vertex.], alt: "A graph with 11 vertices. A single vertex in the center, then five vertices equally spaced around a ring around it, and five more equally spaced around a ring around those. Edges form the sides of a pentagon for the outer ring of vertices. Each outer vertex is also adjacent to two inner vertices: the two on either side of the vertex closest to it. Finally, every inner vertex is also adjacent to the center vertex.", caption: none)


        
          The girth of the graph is 4.


        
      
      
        Explain why we cannot use the same sort of proof we did in Exercise to prove that the graph below is not planar.  Then explain how you know the graph is not planar anyway.


        #figure(figph[A graph with 11 vertices. A single vertex in the center, then five vertices equally spaced around a ring around it, and five more equally spaced around a ring around those. Edges form the sides of a pentagon for the outer ring of vertices and also the inner ring of vertices. Each outer vertex is also adjacent to two inner vertices: the two on either side of the vertex closest to it. Finally, every inner vertex is also adjacent to the center vertex.], alt: "A graph with 11 vertices. A single vertex in the center, then five vertices equally spaced around a ring around it, and five more equally spaced around a ring around those. Edges form the sides of a pentagon for the outer ring of vertices and also the inner ring of vertices. Each outer vertex is also adjacent to two inner vertices: the two on either side of the vertex closest to it. Finally, every inner vertex is also adjacent to the center vertex.", caption: none)


        
          What has happened to the girth?  Careful: we have a different number of edges as well.  Better check Euler's formula.