How to determine if a graph is planar using Kuratowski's theorem?

**Subdivision:** Replacing an edge with a path of length 2 (adding a vertex on the edge). A subdivision of $K_5$ or $K_{3,3}$ means we can obtain one of these graphs by repeatedly subdividing edges. **Why $K_5$ and $K_{3,3}$ are non-planar:** - $K_5$: $V = 5$, $E = 10$. If planar, Euler's formula gives $F = E - V + 2 = 7$. Each face has at least 3 edges, and each edge borders at most 2 faces, so $3F \leq 2E \Rightarrow 21 \leq 20$, contradiction. - $K_{3,3}$: $V = 6$, $E = 9$. Since it's bipartite, no triangles, so each face has at least 4 edges: $4F \leq 2E \Rightarrow 4(5) \leq 18$, contradiction. **Checking for $K_5$ or $K_{3,3}$ subdivisions:** There is no simple polynomial-time algorithm, but for small graphs: 1. Look for a vertex of degree $\geq 4$ (potential $K_5$ center) 2. Look for 3 vertices each connected to the same 3 other vertices (potential $K_{3,3}$) 3. Contract degree-2 vertices (they are subdivisions) and check the resulting graph **Euler's Formula $V - E + F = 2$:** For any connected planar graph. Useful consequences: - $E \leq 3V - 6$ (for $V \geq 3$) - $E \leq 2V - 4$ (for bipartite planar graphs) - A planar graph must have a vertex of degree at most 5 **Fáry's Theorem:** Every planar graph can be drawn with straight-line edges (no bends needed).