Subdivisions and Contractions

Subdivisions and Contractions


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.


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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License