Subdivisions and Contractions
|Definition: A Subdivision of a graph $G$ is the addition of a vertex in the middle of any edge of $G$.|
The graph $H$ is a subdivision of $G$ since $H$ was constructed by adding vertices in between the edges of $G$. This concept of subdividing a graph $G$ is critically important in Kuratowski’s Theorem.
|Definition: A Contraction of a graph $G$ occurs when an edge is brought closer and closer to another vertex until they coincide.|
The graph $H$ is a contraction of $G$, as the top two vertices in $G$ coincide with the bottom two vertices in $G$ to form the contracted graph, $H$.
We also note that if a graph $G$ is planar, then any subdivision of $G$ is also planar, as a subdivision of $G$ does not add any vertices, hence, we can always “untangle” the edges/vertices to produce a planar graph.