By a graph, I mean an undirected multigraph, possibly with some loops.
A graph H is said to be a subdivision of a graph G if H is obtained from G by subdividing some of the edges, that is, replacing the edges by paths having at most their endvertices in common.
Given a graph G, we may construct a topological space R(G), the realization of the graph, from the combinatorial data that G has. Two graphs are said to be homeomorphic to each other if their realizations are homeomorphic as topological spaces.
[Question] Is it true that "Two graphs are homeomorphic iff they have isomorphic subdivisions"?
Intuitively, a graph is homeomorphic to any of its subdivisions (I believe that this is 'geometrically' obvious, but not quite sure how to state and prove this in a rigorous manner), so if two graphs have isomorphic subdivisions, they must be homeomorphic.
But what about the converse? If two graphs are homeomorphic, then does it follow that they have isomorphic subdivisions? This looks like a very hard problem to me, and I'm not even sure why this has to be the case. Maybe one has to assume that given graphs admit piecewise-linear realizations and look for a common pieceswise-linear structure… but I'm not sure.
Is it true that "Two graphs are homeomorphic iff they have isomorphic subdivisions"?
Any advice or reference dealing with this problem is welcome.
Best Answer
Let $G,H$ be graphs such that there exists a homeomorphism $f:|G| \to |H|$ between their topological realizations. We obtain of a subdivision $G'$ of $G$ by subdividing an edge if $f^{-1}(v)$ belongs to that edge for some vertex $v$ of $H$. Similarly, we obtain a subdivision $H'$ of $H$ by subdividing an edge if $f(v)$ belongs to that edge for some vertex $v$ of $G$. Our $f$ above then provides a bijection between the vertex set of $G'$ and that of $H'$. Moreover, if $v,v'$ are two adjacent vertices in $G'$, then we have a corresponding topological edge connecting them in $|G'|$, and this corresponds to a topological edge connecting $f(v),f(v')$ in $|H'|$ through the chain of homeomorphisms $$|G'| \cong |G| \cong |H| \cong |H'|.$$ Therefore $G'$,$H'$ are isomorphic subdivisions of $G,H$.