Homeomorphism (graph theory)

In graph theory, two graphs formula_1 and formula_2 are homeomorphic if there is a graph isomorphism from some subdivision of formula_1 to some subdivision of formula_2. 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.
Subdivision and smoothing.
In general, a subdivision of a graph "G" (sometimes known as an expansion) is a graph resulting from the subdivision of edges in "G". The subdivision of some edge "e" with endpoints {"u","v"} yields a graph containing one new vertex "w", and with an edge set replacing "e" by two new edges, {"u","w"} and {"w","v"}.
For example, the edge "e", with endpoints {"u","v"}:
can be subdivided into two edges, "e"1 and "e"2, connecting to a new vertex "w":
The reverse operation, smoothing out or smoothing a vertex "w" with regards to the pair of edges ("e"1, "e"2) incident on "w", removes both edges containing "w" and replaces ("e"1, "e"2) with a new edge that connects the other endpoints of the pair. Here, it is emphasized that only degree-two (i.e., 2-valent) vertices can be smoothed.
For example, the simple connected graph with two edges, "e"1 {"u","w"} and "e"2 {"w","v"}: 
has a vertex (namely "w") that can be smoothed away, resulting in:
Determining whether for graphs "G" and "H", "H" is homeomorphic to a subgraph of "G", is an NP-complete problem.
Barycentric subdivisions.
The barycentric subdivision subdivides each edge of the graph. This is a special subdivision, as it always results in a bipartite graph. This procedure can be repeated, so that the "n"th barycentric subdivision is the barycentric subdivision of the "n"−1th barycentric subdivision of the graph. The second such subdivision is always a simple graph.
Embedding on a surface.
It is evident that subdividing a graph preserves planarity. Kuratowski's theorem states that 
In fact, a graph homeomorphic to "K"5 or "K"3,3 is called a Kuratowski subgraph.
A generalization, following from the Robertson–Seymour theorem, asserts that for each integer "g", there is a finite obstruction set of graphs formula_5 such that a graph "H" is embeddable on a surface of genus "g" if and only if "H" contains no homeomorphic copy of any of the formula_6. For example, formula_7 consists of the Kuratowski subgraphs.
Example.
In the following example, graph "G" and graph "H" are homeomorphic.
If "G'" is the graph created by subdivision of the outer edges of "G" and "H'" is the graph created by subdivision of the inner edge of "H", then "G'" and "H'" have a similar graph drawing:
Therefore, there exists an isomorphism between "G'" and "H'", meaning "G" and "H" are homeomorphic.