# 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

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.

## 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 .

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

## 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 .

## See also

## Web links

- Béla Bollobás:
*Subdivision*. In:*PlanetMath .*(English) - Ed Pegg, Jr .:
*Edge splitting*. In:*MathWorld*(English).