# 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 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\ne 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 |
---|---|

Canonical name | GraphHomeomorphism |

Date of creation | 2013-03-22 18:02:02 |

Last modified on | 2013-03-22 18:02:02 |

Owner | Ziosilvio (18733) |

Last modified by | Ziosilvio (18733) |

Numerical id | 8 |

Author | Ziosilvio (18733) |

Entry type | Definition |

Classification | msc 05C99 |

Defines | simple subdivision |