# Rooted Tree Isomorphism Algorithm

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $$S_{u}$$ be the number of vertices in the rooted subtree of vertex $$u$$. Namely, the size of the subtree of $$u$$. Now Let $$L_{i}$$ = {$$S_{u}$$ : $$lvl(u)$$ = $$i$$}. Here, $$lvl(v)$$ denotes the level of $$v$$. Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $$H_{1}$$ and $$H_{2}$$ be the heights of the rooted trees $$T_{1}$$ and $$T_{2}$$, respectively. $$T_{1}$$ and $$T_{2}$$ are isomorphic if and only if $$H_{1} = H_{2}$$ and for every integer $$i \in [ \,1,H_{1}] \,$$, the multiset $$L_{i}$$ of $$T_{1}$$ and that of $$T_{2}$$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.

• Yeah, that`s what i meant. – Mateus Buarque Mar 13 at 14:36