Homeomorphism (graph theory)

Encyclopedia : H : HO : HOM : Homeomorphism (graph theory)

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 yields a graph containing one new vertex v, and with an edge set replacing e by two new edges with endpoints and .

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

Homeomorphism (graph theory)

See also