Let be a simple undirected graph. A simple subdivision is the replacement of an edge with a pair of edges , being a new vertex, i.e., . The reverse operation of a simple subdivision is an edge-contraction through a vertex of degree 2.
Two graphs , are homeomorphic if can be transformed into 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, and are homeomorphic if there exists a third graph such that both and can be obtained from via a finite sequence of edge-contractions through vertices of degree 2.
If a graph has a subgraph which is homeomorphic to a graph having no vertices of degree 2, then is a minor of . The vice versa is not true: as a counterexample, the Petersen graph has as a minor, but no subgraph homeomorphic to . This happens because a graph homeomorphism cannot change the number of vertices of degree : since all the vertices of have degree 4 and all the vertices of the Petersen graph have degree 3, no subgraph of the Petersen graph can be homeomorphic to .
|Date of creation||2013-03-22 18:02:02|
|Last modified on||2013-03-22 18:02:02|
|Last modified by||Ziosilvio (18733)|