Let $G=(V,E)$ be a graph.
- The edge subdivision operation for an edge $\{u, v\} \in E$ is the deletion of $\{u, v\}$ from $G$ and the addition of two edges $\{u, w\}$ and $\{w, v\}$ along with the new vertex $w$.
- A graph which has been derived from $G$ by a sequence of edge subdivision operations is called a subdivision of $G$.
- Two graphs $G$ and $G'$ are homeomorphic if there is a graph isomorphism from some subdivision of $G$ to some subdivision of $G'$.
The following example illustrates that $G$ is not a subdivision of $H$, and $H$ is also not a subdivision of $G$, but $G$ and $H$ are homeomorphic since $G'$ is isomorphic to $H'$ where $G'$ and $H'$ are some subdivisions of $G$ and $H$ respectively.
A well known Kuratowski's Theorem stated that a graph $G$ is planar if and only if $G$ does not contain a subgraph that is a subdivision of $K_{5}$ or of $K_{3,3}$.
Homeomorphism (graph theory) (Wiki) describes Kuratowski's Theorem with the terminology homeomorphism. It said:
Kuratowski's theorem states that: A finite graph is planar if and only
if it contains no subgraph homeomorphic to $K_5$ (complete graph on
five vertices) or $K_{3,3}$ (complete bipartite graph on six vertices,
three of which connect to each of the other three).
But by the definition of graph homeomorphic, it seems to assert that, in Kuratowski's theorem, a graph $G$ is planar if and only if it does not contain a subgraph whose subdivision ($\color{red}{not~ refer~ subgraph!}$) is isomorphic to a subdivision of $K_5$ or $K_{3,3}$.
So I'm quite puzzled. I feel that the use of the term "homeomorphism" might not align with Kuratowski's original intent. There are some subtle distinctions, and I believe they are not equivalent from a literal standpoint.
I would like to ask, what does 'subgraph homeomorphic to' mean here?
If it refers to a subgraph of $G$ is a subdivision of $K_{3,3}$ and $K_5$, it is OK. However, if it says that some subdivision of a subgraph of $G$ is some subdivision of $K_{3,3}$ or $K_5$, then I am confused.
Best Answer
The more direct way to state Kuratowski's condition for non-planar graphs is "$G$ has a subgraph $H$ which is isomorphic to a subdivision of $K_{3,3}$ or $K_5$". If we were to say "$G$ has a subgraph $H$ which is homeomorphic to $K_{3,3}$ or $K_5$", we'd be saying "$G$ has a subgraph $H$ which has a subdivision isomorphic to a subdivision of $K_{3,3}$ or $K_5$": this needlessly subdivides the subgraph of $G$.
Nevertheless, the two forms of the condition are equivalent. If $H$ has a subdivision $H'$ isomorphic to a subdivision of $K_{3,3}$ or $K_5$, then $H$ itself is isomorphic to a (different) subdivision of $K_{3,3}$ or $K_5$. In fact, the same thing is true if we replace $K_{3,3}$ or $K_5$ by any graph with minimum degree at least $3$.
The idea is that $H$, $H'$, and every intermediate subdivision maintain a correspondence between their degree-$3$-or-more vertices, which are never changed; the only thing that varies is the length of the paths between them. (These paths are just edges in the case of $K_{3,3}$ or $K_5$.) So $H$ must already have the right number of degree-$3$-or-more vertices, with the right pairs of them connected by internally disjoint paths, which means it already has the structure of the subdivision we want.