Subdivisions and Contractions

# Subdivisions and Contractions

## Subdivisions

Definition: A Subdivision of a graph $G$ is the addition of a vertex in the middle of any edge of $G$. |

For example:

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.

## Contractions

Definition: A Contraction of a graph $G$ occurs when an edge is brought closer and closer to another vertex until they coincide. |

For example:

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.