Homeomorphism (graph theory)
In graph theory, a homeomorphism of a graph refers to the result of subdividing the edges of the graph. A subdivision of an edge consists of removing the edge and replacing it with a path of length two or more connecting the same two endpoints as the original edge. Specifically, an edge {u, v} is subdivided by replacing it with a vertex w and edges {u, w} and {w, v}. The vertex w is a new vertex of degree 2.
Two graphs G and H are homeomorphic if they can both be obtained from the same graph by a sequence of subdivisions. In other words, there exists a graph K such that both G and H can be obtained from K by subdividing some of its edges. This implies that G and H are topologically the same, even if they have a different number of vertices and edges. The relation "is homeomorphic to" is an equivalence relation.
Homeomorphisms are important in graph theory because they preserve several key graph properties. For example, if two graphs are homeomorphic, then one is planar if and only if the other is planar. This property is fundamental to Wagner's theorem, which characterizes planar graphs as those which do not contain K5 or K3,3 as minors. Kuratowski's theorem similarly characterizes planar graphs, stating that a graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3,3. Thus, homeomorphisms provide a way to recognize planar graphs by detecting specific non-planar configurations.