# Counting Walks in Regular Graphs

I am reading M. Ram Murty's paper on Ramanujan Graphs: http://www.mast.queensu.ca/~murty/ramanujan.pdf and I am having trouble in a particular section, which is Section 6 on page 17 titled Counting walks in reguar graphs (it's a rather short section of about half page). In particular, I do not understand the conclusion that $$A_1A_r=A_{r+1}+(k-1)A_{r-1}$$ and what follows.

To give some context, we are considering a $k-$regular graph $X$ and its associated adjacency matrix $A$. We wish to construct a family of matrices (of same size as $A$, the number of vertices)$\{A_r\}$ such that the $(x,y)$-th coordinate of $A_i$ is the number of proper walks of length $i$ between the vertices $x$ and $y$. Here, proper walk means a walk that does not backtrack, its is however permitted at all times though that, for a walk, proper or otherwise, to have repeated vertices, at least this is the way Murty defined it earlier.

Here is what I have. the quantity $A_1A_r$ enumerates the number of walks of length $r+1$ which are proper up to length $r$ but may become improper at the last step, i.e. it can backtrack at the last step. Now on the right hand side we have $A_{r+1}$ which enumerates the number of proper walks of length $r+1$, plus $(k-1)$ times the matrix that enumerates proper walks of length $r-1$, here understand we must add more to $A_{r+1}$ since this only has strictly proper walks, but I am having trouble understanding why it is the quantity $(k-1)A_{r-1}$ that we need.

Another thing, the equation $A^2=A_2+kI$ makes sense, as we need to add the improper walks of length 2 which come out from a vertex one step then backtrack immediately after, and for each vertex we have exactly $k$ of these. Now, if we use the fact that $A_0=I$ and $A_1=A$, then $A_1A_1=A^2$. Now use the equation which I don't understand yet $A_1A_r=A_{r+1}+(k-1)A_{r-1}$ and take $r=1$, we have $$A_1A_1=A_2+(k-1)I$$ We have just shown $A_1A_1=A^2$ thus $A^2=A_2+(k-1)I$, but this is a contradiction to $A^2=A_2+kI$. What am I missing here? Any help is appreciated!!

In addition, I also do not understand Proposition 11 at the end either, and help on that would be appreciated as well.

Given that $A_1 A_r$ gives walks of length $r+1$ that may be improper only in the last step, the difference $A_1 A_r - A_{r+1}$ should count walks that are improper in the last step. These walks consist of a proper walk for $r-1$ steps, followed by taking any non-backtracking edge from the last vertex and immediately retracing it. There are $k-1$ choices for this edge, so there are $(k-1) A_{r-1}$ such walks.

I think this equation can only be valid for $r>1$, however, explaining why you run into trouble with your $r=1$ example. The problem is that if $r-1=0$, then "a proper walk for $r-1$ steps, followed by taking any non-backtracking edge from the last vertex and immediately retracing it" has $k$ choices for the non-backtracking edge: a proper walk for $0$ steps doesn't have anywhere to backtrack, so any of the $k$ edges from the endpoint is a valid edge to take and then double back on.

The proposition at the end of that page is essentially a standard way of using a recurrence relation to obtain a generating function. Define $F(t) = \sum_{r \ge 0} A_r t^r$. Then we can use the identity $A_1A_r=A_{r+1}+(k-1)A_{r-1}$ to write down an equation that $F(t)$ must satisfy:

\begin{align} F(t) &= A_0 + A_1t + A_2t^2 + \sum_{r \ge 3} A_r t^r \\ &= A_0 + A_1t + A_2t^2 + \sum_{r \ge 3} (A_1 A_{r-1} - (k-1) A_{r-2}) t^r \\ &= A_0 + A_1t + A_2t^2 + A_1 t \sum_{r \ge 3} A_{r-1} t^{r-1} - (k-1)t^2 \sum_{r \ge 3} A_{r-2} t^{r-2} \\ &= A_0 + A_1t + A_2t^2 + A_1 t \left(F(t) - A_0 - A_1 t\right) - (k-1)t^2 (F(t) - A_0) \end{align} and by solving for $F(t)$ and substituting in the initial conditions for $A_0$, $A_1$, $A_2$, we should get the equation in Proposition 11.

• ah, I think I understand this now. Thanks a lot! Commented Apr 17, 2017 at 3:15
• Not to make it seem that you haven't helped in solving the question yet, (quite the contrary), Have you any idea how the proposition at the end is derived? Commented Apr 17, 2017 at 3:16
• I've edited my answer to address that. Commented Apr 17, 2017 at 3:27
• Thank you very much for your assistance. Commented Apr 17, 2017 at 13:53