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
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