# A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to the number of walks of $T_2$ starting at $r_2$ of length $k$. Is it true that $T_1$ and $T_2$ are isomorphic as rooted trees?

It seems to me strange that this would be true and I cannot find any mention of it. On the other hand, I can't seem to come up with a counterexample.

EDIT: Apologies! I should have said that walks are not assumed to be simple or closed! A walk is just a sequence of adjacent edges, edges and vertices may be repeated and the ending point does not matter.

-
Can you be a bit more specific about what you mean by a walk of length $k$? some obvious interpretations admit obvious counterexamples, so some clarity would help. – Vladimir Dotsenko Jan 12 at 12:35
Just a sequence of edges $(v_1,v_2),(v_2,v_3),\dots,(v_{k-2},v_{k-1})$. And I'm also requiring that $v_1$ be the root. The paths are allowed to end wherever, and any amount of backtracking is allowed; these walks do not have to be simple. They can repeat edges and vertices. It's quite possible I missed some easy counterexample. – batconjurer Jan 12 at 12:53
As for me, possible counterexanples probably can be found among pairs of isospectral trees. Do you have any software to check whether your condition is satisfied? If so, I would suggest to test some pairs from, e.g., pubs.acs.org/doi/pdf/10.1021/ci970242r (parhaps, those on Fig. 5?). – Ilya Bogdanov Jan 12 at 13:13
Sure, I can give that a shot. – batconjurer Jan 12 at 13:35

Take a 9-cycle with vertices $\{0,\ldots,8\}$ and join new vertices of degree one to 0, 3, 6. Delete the vertex 8 from the cycle, producing a tree $T$ on 11 vertices. Then $T\backslash 2\cong T\backslash 5$, but no automorphism of $T$ maps 2 to 5.
Now there is a theorem that if $u$ and $v$ are vertices in graph $X$ and $X\backslash u$ and $X\backslash v$ are cospectral and their complements are cospectral, the generating functions for closed walks at $u$ and for all walks at $u$ are equal to the corresponding generating functions for walks at $v$. (This is a consequence of results from chapter 4 in my book "Algebraic Combinatorics".)
I'm a bit confused by your answer. First of all, $T$ was formed by deleting vertex 8, so I don't know what it means for $T$ to have no automorphism taking 5 to 8. If $T$ is the graph with 8 still in, then indeed $T\setminus 5\cong T\setminus 8$, but no roots are specified for me to check the condition. Clarification would be greatly appreciated. (Also, I should apologize as I added a clarification as a comment earlier that I should have put in the question. Walks are not assumed to be simple. I don't know if that changes your example) – batconjurer Jan 12 at 14:39