Confusion in understanding two equivalent statements of Kuratowski’s Theorem

graph theoryplanar-graphs

Two graphs G and H are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of H.

Kuratowski's theorem:
Statement 1:
A graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 or K3,3

Statement 2:
A graph is planar if and only if it contains no subdivision of K5 or K3,3

Both statements are equivalent as given in West's book but I have the following doubt

MY DOUBT
By statement 1 and the definition of homemorphism of two graphs, it follows that
A graph is planar iff it does not contain any subgraph whose some subdivision is isomorphic to some subdivision of K5 or K3,3 i.e. it may happen that there is no subgraph which itself is a subdivision of K5 or K3,3 but some vertices can be added to the graph so that it becomes a subdivion of K5 or K3,3. But then it is not the same as Statement 2.

Where am I wrong in my conception or understanding? Please clarify. Thanks for any help.

Best Answer

You are right that the statements "$G$ is homeomorphic to $H$" and "$G$ is isomorphic to a subdivision of $H$" are not equivalent in general, but they are equivalent if $H$ has minimum degree at least $3$.

In that case, suppose we find an isomorphism between a subdivision $G'$ of $G$ and a subdivision $H'$ of $H$. Let $n = |V(H)|$. Then $G'$ and $H'$ must both have $n$ vertices of degree $\ge 3$, corresponding to the vertices of $H$, with some paths between them. All $n$ of these vertices in $G'$ must already have been present in $G$, because they cannot be introduced by subdividing - $G$ just possibly had shorter paths between them, maybe even single edges. Meanwhile, in $H$, all paths present between these $n$ vertices were just single edges, because $H$ has no degree-$2$ vertices. Therefore $G$ is isomorphic to a subdivision of $H$.

In particular, "$G$ is homeomorphic to $K_{5}$ or $K_{3,3}$" and "$G$ is isomorphic to a subdivision of $K_5$ or $K_{3,3}$" are equivalent statements.

A a result, "A graph is planar iff it has no subgraph homeomorphic to $K_5$ or $K_{3,3}$" and "A graph is planar iff it contains no subdivision of $K_5$ or $K_{3,3}$" are equivalent characterizations. Both are saying that a graph is planar iff it has no subgraph $G$ of the type in the previous paragraph.

Related Question