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\notin V$.The reverse operation of a simple subdivisionis an edge-contraction through a vertex of degree 2.

Two graphs $G_1$, $G_2$ are homeomorphicif $G_1$ can be transformed into $G_2$via a finite sequence of simple subdivisionsand 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 homeomorphicif 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 graphhas $K_5$ as a minor, but no subgraph homeomorphic to $K_5$.This happens because a graph homeomorphismcannot change the number of vertices of degree $d\ne 2$:since all the vertices of $K_5$ have degree 4and all the vertices of the Petersen graph have degree 3,no subgraph of the Petersen graph can be homeomorphic to $K_5$.