Part (a): Proving the Existence of Non-adjacent Neighbors

For a planar graph $G$, let $v$ be a vertex of degree 5, and let $N(v) = \{u_1, u_2, u_3, u_4, u_5\}$ denote the set of neighbors of $v$. Since $v$ is degree 5, there are at most 10 edges among these neighbors. However, for $G$ to be planar, it must satisfy Euler's formula:

$|V| - |E| + |F| = 2,$

where $|F|$ is the number of faces. Additionally, a planar graph cannot contain a complete subgraph $K_5$ as a minor, meaning $N(v)$ cannot induce $K_5$. Thus, it is impossible for all pairs of neighbors $u_i, u_j$ to be connected. Therefore, there must exist two neighbors $u$ and $w$ such that $uw \notin E(G)$.

---

Part (b): Planarity of $G_v$

The graph $G_v$ is obtained by removing the vertices $u, v, w$ from $G$ and introducing a single new vertex $v^*$ adjacent to:

$N(v) \cup N(u) \cup N(w) \setminus \{u, v, w\}.$

Key Argument for Planarity:

• Removing $v$ and its neighbors $u, w$ reduces the graph $G$ locally but does not fundamentally alter its planarity because planarity is preserved under edge contraction and vertex removal.
• Adding $v^*$ back to reconnect the remaining neighbors respects planarity because $v^*$ is a single vertex that does not create crossings that would violate the planar embedding.

By definition, the reconstruction of the graph with $v^*$ does not exceed the conditions of Euler's formula or result in forbidden minors like $K_5$ or $K_{3,3}$. Thus, $G_v$ remains planar.

---

Part (c): 5-Coloring $G$ from $G_v$

Procedure for 5-Coloring $G$:

1. Begin with a valid 5-coloring of $G_v$.
2. Since $v^*$ replaced $u, v, w$, assign the colors of $u, v, w$ based on the color of $v^*$:
   • Remove $v^*$'s color from the available 5 colors.
   • Recolor $u, v, w$ to avoid conflicts with their neighbors.
   • This step is always feasible because $v$ has only 5 neighbors and hence at least one available color for each vertex.

Algorithm for 5-Coloring Planar Graphs:

1. Start with a planar graph $G$.
2. Identify a vertex $v$ of degree at most 5 (exists by the Four Color Theorem's structure).
3. Reduce $G$ by replacing $v$ and up to two of its neighbors with $v^*$, forming $G_v$.
4. Recursively 5-color $G_v$.
5. Expand $G_v$ back to $G$ by restoring $u, v, w$ and assigning colors as described.

Complexity Discussion:

• Each step of removing $v$ and its neighbors reduces the graph's size. If $G$ has $n$ vertices, the recursion depth is $O(n)$.
• Each coloring step involves checking the neighbors of at most 5 vertices, making it $O(1)$ for each vertex.
• The overall complexity is $O(n)$, which is efficient for planar graphs.

---

Follow-Up Questions:

1. Why can Euler's formula help determine the absence of $K_5$ in planar graphs?
2. How does the degree constraint of planar graphs influence the coloring algorithm?
3. Can the proposed method generalize to graphs of maximum degree $\Delta \geq 6$?
4. What are the key differences between this approach and methods using Kempe chains?
5. How does the recursive 5-coloring ensure correctness without backtracking?

---

Tip:

When analyzing planar graph properties, focus on Euler's formula and forbidden minors like $K_5$ and $K_{3,3}$, as they provide structural insights critical to algorithm design.