Graph Subdivision

Definition (Graph Subdivision)

A subdivision of graph $G$ is obtained by placing vertices in the middle of some of its edges.

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

Lemma (Subdivisions Preserve Planarity)

If $G^{\prime }$ is a subdivision of $G$, then $G^{\prime }$ is planar $⟺$ $G$ is planar.

Proof: Given a plane embedding of $G$ we can add vertices of in the middles of $E(G)$ to get the embedding of $G^{\prime }$. Given the embedding of $G^{\prime }$, we remove vertices and join edges to get the embedding of $G$.