How can I check that two simple connected graphs are homeomorphic? I know the defenition of homeomorfism, but I can't figure out when to stop subdividing, algoritmically. I need here some stopping inequality.
I've made a hypothesis:
$$ G_1 ~ is ~ homeomorphic ~ to ~ G_2 \Leftrightarrow \forall k \in \mathbb N \backslash \{2\} ~~ D_{G_1}^k = D_{G_2}^k $$
where $G_1, G_2$ both simple connected graphs and $D_{G}^k$ is number of vertices of degree $k$ in graph $G$.
But I can neither proof it from right to left, nor make a counter-example.
UPD: The counter-example had been given, but the suggestions on how to stop subdividing still needed. Alternative approaches would be appreciated, too.
UPD2: I have now a chain of necessary conditions:
if $G_1$ is homeomorphic to $G_2$ then
$
\bullet ~ \forall k \in \mathbb N \backslash \{2\} ~~ D_{G_1}^k = D_{G_2}^k
$
$
\bullet ~ |E_1|-|V_1| = |E_2| – |V_2|
$
$\bullet$ graphs $G_1'$ and $G_2'$ obtained by smoothing $G_1$ and $G_2$ are isomorphic.
UPD3: I've built implementation of homeomorphism searching in Scala. You can freely get it (and contribute to it!) at github. It's quite dummy, but I wouldn't develop it much futher.
Best Answer
Your hypothesis is not true. A counter-example would be $K_{3,3}$ and the graph given by the following edgeset: $$ (1,2)\; (1,3)\; (1,4)\; (2,3)\; (2,5)\; (3,6)\; (4,5)\; (4,6)\; (5,6) $$ Both of these graphs have $6$ vertices each with degree $3$, but they are not homeomorphic.
It is true, though that $$ G_1 \;\mathrm{homeomorphic\ to}\; G_2 \;\implies\; (\forall k \in \mathbb{N}\setminus \{2\})\;\; D^k_{G_1} = D^k_{G_2} $$
so that should be the first check in your algorithm. I believe that instead of trying to find a common subdivision between two graphs $G_1$ and $G_2$ (by adding degree-$2$ vertices on existing edges), it may be easier to go in the other direction and remove all degree-$2$ vertices (undo all the possible subdivisions in $G_1$ and $G_2$). I believe that if $G_1$ and $G_2$ are homeomorphic, then the resulting graphs of un-subdividing all possible edges in those graphs will be isomorphic. Algorithms on checking if two graphs are isomorphic, though potentially complicated, are much more documented then graph homeomorphism algorithms (there is a wikipedia page dedicated to the problem of checking if two graphs are isomorphic).