Why is a non-planar graph still non-planar after subdividing it?

67 Views Asked by At

A graph $H$ is said to be a subdivision of a graph $G$ if $H$ can be obtained from G by successively deleting an edge in $G$, and replacing that edge with a length 2 path (whose central vertex was not originally part of $G$). I have learnt that if $G$ is non-planar, any subdivision $H$ of $G$ is non-planar as well. However, I am not seeing this. For example, if 2 edges cross at a certain point, it seems we could subdivide both of these edges along the point at which they intersect, such that these edges no longer violate planarity. This doesn't seem precluded by the definition of a subdivision, as the definition says we can cut a sequence of edges for each subdivision, so when it talks about the vertices not being in $G$, neither of the central vertices we have added in these paths were in $G$, even though these central vertices coincide. Could someone explain why my "Counterexample" isn't really a counterexample, and why any subdivision of $G$ would be planar on a more formal level?

1

There are 1 best solutions below

0
On BEST ANSWER

Your counterexample is not a counterexample for two reasons. The first is that the statement "if $G$ is planar, any subdivision $H$ of $G$ is planar as well" does not imply the statement "if $G$ is non-planar, every subdivision $H$ of $G$ is non-planar as well". The second is that if we have two edges $e_1$ and $e_2$ that intersect, we would add two vertices when subdividing them, one for $e_1$ and one for $e_2$. In your counterexample, you seem to assume that these vertices are the same when, in fact, they are distinct!