# graph homeomorphism

Let $G=(V,E)$ be a simple undirected graph. A simple subdivision is the replacement of an edge $(x,y)\in E$ with a pair of edges $(x,z),(z,y)$, $z$ being a new vertex, i.e., $z\not\in V$. The reverse operation of a simple subdivision is an edge-contraction through a vertex of degree 2.

Two graphs $G_{1}$, $G_{2}$ are homeomorphic if $G_{1}$ can be transformed into $G_{2}$ via a finite sequence of simple subdivisions and edge-contractions through vertices of degree 2. It is easy to see that graph homeomorphism is an equivalence relation.

Equivalently, $G_{1}$ and $G_{2}$ are homeomorphic if there exists a third graph $G_{3}$ such that both $G_{1}$ and $G_{2}$ can be obtained from $G_{3}$ via a finite sequence of edge-contractions through vertices of degree 2.

If a graph $G$ has a subgraph $H$ which is homeomorphic to a graph $G^{\prime}$ having no vertices of degree 2, then $G^{\prime}$ is a minor of $G$. The vice versa is not true: as a counterexample, the Petersen graph has $K_{5}$ as a minor, but no subgraph homeomorphic to $K_{5}$. This happens because a graph homeomorphism cannot change the number of vertices of degree $d\neq 2$: since all the vertices of $K_{5}$ have degree 4 and all the vertices of the Petersen graph have degree 3, no subgraph of the Petersen graph can be homeomorphic to $K_{5}$.

Title graph homeomorphism GraphHomeomorphism 2013-03-22 18:02:02 2013-03-22 18:02:02 Ziosilvio (18733) Ziosilvio (18733) 8 Ziosilvio (18733) Definition msc 05C99 simple subdivision