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

See also

• Minor (graph theory)

Graph theory

Homeomorfizm grafów | Phép đồng phôi (lý thuyết đồ thị)