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., $K<em>4$, $K</em>5$).
• Removing a vertex from a complete graph $K<em>n$ results in $K</em>{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, $3v<em>3 + 2v</em>4 + v<em>5 = 12 + v</em>7 + 2v<em>8 + 3v</em>9 + 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<em>{i} deg(v</em>i) = 2e$
• In terms of $v<em>i$, this is $3v</em>3 + 4v<em>4 + 5v</em>5 + 6v<em>6 + 7v</em>7 + \dots = 2e$
• For a maximal planar graph, $e = 3v - 6$, so $2e = 6v - 12$.
• Also, $v = v<em>3 + v</em>4 + v<em>5 + v</em>6 + v<em>7 + \dots$, so $6v = 6v</em>3 + 6v<em>4 + 6v</em>5 + 6v<em>6 + 6v</em>7 + \dots$
• Therefore, $3v<em>3 + 4v</em>4 + 5v<em>5 + 6v</em>6 + 7v<em>7 + \dots = 6v</em>3 + 6v<em>4 + 6v</em>5 + 6v<em>6 + 6v</em>7 + \dots - 12$
• Rearranging terms leads to the desired result:
  • $3v<em>3 + 2v</em>4 + v<em>5 = 12 + v</em>7 + 2v<em>8 + 3v</em>9 + 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 $3v<em>3 + 2v</em>4 + 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.