Graph Theory Exam Notes

Graph Theory and Induction Proofs

Avoiding Pitfalls in Induction Proofs

  • When constructing induction arguments for graphs, avoid referring to the "last vertex" or "last edge" added.
  • While such arguments can be made rigorous, they require significant effort to describe graph construction or redrawing processes.
  • Simply stating "remove the last edge" or "remove the last vertex" is insufficient for a rigorous proof.

Induction on Vertices

  • Matt's question: Can induction on vertices or edges be used?
    • Answer: Both can work, but may require breaking into cases.
  • Assume the statement is true for all connected graphs with k vertices.
  • Consider a graph G with k+1 vertices.
  • Goal: Remove a vertex to apply the induction hypothesis.
  • Removing a vertex also requires removing its incident edges.
  • Ideal scenario: Removing a vertex and its edges results in a graph where restoring them is straightforward (adding one vertex and one edge).
  • Alternative scenario: Removing a vertex may require careful selection due to graph structure.
  • Strategy: Remove a degree-2 vertex to maintain connectivity.
  • Removing a vertex might disconnect the graph, requiring separate analysis of components.
  • Breaking into cases is a viable problem-solving strategy.

Complete Graphs

  • Consideration: Complete graphs (e.g., K4, K5).
  • Removing a vertex from a complete graph Kn results in K{n-1}.

Equivalence Proofs

  • To show two statements are equivalent, prove that the first implies the second and vice versa.
  • For multiple statements, establish a cycle of implications (e.g., 1 implies 2, 2 implies 3, 3 implies 1).
  • Alternatively, show that one statement implies all others and that all others imply the first.

Grading and Content

  • Perfect scores do not require perfect solutions to every problem.
  • Grades are based on content and presentation.
  • Aim for approximately 90% accuracy with well-presented solutions.

Planar Graphs and Straight-Line Embeddings

  • Problem 31: Prove that every planar graph can be embedded in the plane with straight-line edges.
  • Source: "Pearls in Graph Theory"
  • Goal: Show that any planar graph can be redrawn with all edges as straight line segments.
  • Planar graphs can initially be drawn with curved edges, but the aim is to demonstrate that they can always be redrawn with straight lines.

Maximal Planar Graphs

  • Definition: A maximal planar graph has the maximum possible number of edges for a given number of vertices while remaining planar.
  • A planar graph is maximal planar if no additional edge can be added without introducing crossings.

Properties of Maximal Planar Graphs (with at least four vertices)

  • e = 3v - 6, where e is the number of edges and v is the number of vertices.
  • All faces are triangles.
  • This leads to the formula e = 3v - 6.
    • In the original proof of e \leq 3v - 6, a fencing argument was used.
    • The number of fence sides to be painted was counted in two ways: 2e (exact) and 3f (lower bound, where f is the number of faces).
    • This yielded the inequality 2e \geq 3f, which, combined with Euler's formula, led to e \leq 3v - 6.
    • For maximal planar graphs, every face is a triangle, so 2e = 3f.
  • Vertices cannot have degree 0, 1, or 2.

Lemma

  • A lemma is a theorem that is primarily of interest as a step in a longer proof.
  • Let v_i be the number of vertices of degree i.
  • Then, 3v3 + 2v4 + v5 = 12 + v7 + 2v8 + 3v9 + 4v_{10} + \dots

Proof of Lemma

  • Recall the Handshake Theorem: The sum of the degrees of the vertices in a graph is twice the number of edges.
    • \sum{i} deg(vi) = 2e
  • In terms of vi, this is 3v3 + 4v4 + 5v5 + 6v6 + 7v7 + \dots = 2e
  • For a maximal planar graph, e = 3v - 6, so 2e = 6v - 12.
  • Also, v = v3 + v4 + v5 + v6 + v7 + \dots, so 6v = 6v3 + 6v4 + 6v5 + 6v6 + 6v7 + \dots
  • Therefore, 3v3 + 4v4 + 5v5 + 6v6 + 7v7 + \dots = 6v3 + 6v4 + 6v5 + 6v6 + 6v7 + \dots - 12
  • Rearranging terms leads to the desired result:
    • 3v3 + 2v4 + v5 = 12 + v7 + 2v8 + 3v9 + 4v_{10} + \dots

Corollary

  • Corollary: A result that follows almost directly from another result.
  • If G is a maximal planar graph with at least four vertices, then G has at least four vertices of degree at most five.
  • Proof is discussed by consider the different ways to satisfy 3v3 + 2v4 + v_5 = 12

Wagner's Theorem

  • Wagner's Theorem: Every planar graph can be drawn in the plane with straight-line edges.

  • Proof by induction on the number of vertices.

    • Base case: K_4 (can be drawn with straight lines).
    • Induction hypothesis: Assume all planar graphs with up to k vertices are straight-line drawable.

  • Let G be a planar graph with k+1 vertices.

    • If G isn't maximal planar, add edges to make it maximal planar.
    • By the corollary, G has at least four vertices of degree at most five.
    • Since all ofs faces are triangles, G has a vertex of degree at most five that's not on the exterior face. Call that vertex h.
    • Consider the graph obtained by removing that vertex.
      • If h is of degree 3, then you have a triangle.
      • If h is of degree 4, then you have a quadrilateral.
      • If h is of degree 5, then you have a pentagon.

  • The key step involves considering what happens when h is degree three, four, or five, and paying careful attention to whether the polygon in question is convex or concave: if the polygon is concave, select the placement of the removed vertex, h, carefully to ensure that connecting it to all neighbors creates no crossings.

  • Every theorem also shows that every planar graph can be drawn as a coin graph.