MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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., (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
up vote 8 down vote accepted

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".)

So vertices 2 and 5 cannot be distinguished by your criterion. (My example is quite likely not minimal.)

share|cite|improve this answer
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
@Ilya Bogdanov: thanks, I've made the appropriate edits. – Chris Godsil Jan 12 at 15:04
@Ilya Bogdanov : Chris and I found this example in our first paper together (1975), see Fig 7 at . I'm sure it is the first example where the two rooted trees are isomorphic if the root is ignored, but plausibly there are smaller examples without that property. – Brendan McKay Jan 12 at 19:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.