# Subdivision graph

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 .

## Definitions

### Subdivision graph

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 ${\ displaystyle G = (V, E)}$ ${\ displaystyle e = \ {u, v \} \ in E}$ ${\ displaystyle e_ {1}}$ ${\ displaystyle e_ {2}}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle w \ notin V}$ ${\ displaystyle G '= (V', E ')}$ ${\ displaystyle V '= V \ cup \ {w \}}$ and the new set of edges

${\ displaystyle E '= E \ setminus \ {e \} \ cup \ {e_ {1}, e_ {2} \}}$ ,

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. ${\ displaystyle e_ {1} = \ {u, w \}}$ ${\ displaystyle e_ {2} = \ {w, v \}}$ ### 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.

## Examples

The following two graphs and are homeomorphic because they share the common subdivision graph . The homeomorphism origin of the two graphs is the graph . ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle C}$ ${\ displaystyle D}$ All circular graphs are also homeomorphic to one another with the graph as the homeomorphic origin. ${\ displaystyle C_ {n}}$ ${\ displaystyle n \ geq 2}$ ${\ displaystyle C_ {2}}$ ## use

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 . ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {3,3}}$ 