Homeomorphism (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, a homeomorphism exists between two graphs G and G′ if there exists a graph H such that both G and G′ are subdivisions of that graph. If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology.

In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints {u,w} yields a graph containing one new vertex v, and with an edge set replacing e by two new edges with endpoints {u,v} and {v,w}.

For example, if we have the graph G₁

*--*--*--*

and G₂

*--*--*--*--*

these two graphs are homeomorphic, since given the graph

*---*---*
  x   y

subdividing edge x gives G₁, and subdividing both x and y gives G₂.

[edit] See also

• Minor (graph theory)