# Subdivision graph

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 .

## Definitions

### Subdivision graph

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 ${\ 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}}$