Subdivision graph

from Wikipedia, the free encyclopedia
Subdivision graph of the complete graph K 5 , which is created by subdividing all edges

A subdivision graph is graph theory , a graph , by edge subdivision was created from a different graph. Two graphs are called homeomorphic if they have subdivision graphs that are isomorphic . Subdivision graphs play an important role in Kuratowski's theorem and in the Hajós conjecture , among others .


Subdivision graph

Graph subdivision step1.svg
Graph subdivision step2.svg
Edge before and after subdivision

Is an undirected graph , then is meant by a subdivision of an edge of the replacement of this edge by two new edges and that the two nodes and the distal edge with a new node connect. This creates a new graph with the new set of nodes

and the new set of edges


where and are. A subdivision graph of a graph is now a graph that arises from it by (zero, one or more times) edge subdivision.

Homeomorphism of graphs

Two graphs are called homeomorphic if there are subdivision graphs of these two graphs that are isomorphic to each other . The homeomorphic origin of a graph is the smallest graph that is homeomorphic to it. The homeomorphism origin of a graph can be determined by repeatedly removing nodes of degree two ( excluding loops ) and inserting an edge connecting the two neighboring nodes of the removed node. Two graphs are now homeomorphic if and only if their homeomorphism origins are isomorphic.


The following two graphs and are homeomorphic because they share the common subdivision graph . The homeomorphism origin of the two graphs is the graph .

All circular graphs are also homeomorphic to one another with the graph as the homeomorphic origin.


Subdivision graphs play an important role in Kuratowski's theorem . According to this theorem, a finite graph is planar if and only if it does not contain a subgraph that has been created by subdividing the complete graph or the completely bipartite graph . They also serve to define topological minors .

See also

Web links