The following is an exercise (Exercise #2 (a), Chapter 3, page 28) from Richard Stanley's Algebraic Combinatorics.
Let $G$ be a finite graph (allowing loops and multiple edges). Suppose that there is some integer $l > 0$ such that the number of walks of length $l$ from any fixed vertex u to any fixed vertex v is independent of u and v. Show that G has the same number k of edges between any two vertices (including k loops at each vertex).
My approach:
Let $A$ be the adjacency matrix of the graph $G$. The given condition implies that $\exists \ \ l > 0$ such that $A^l = cJ$, where $c$ is a non-negative integer and $J$ is the all one matrix. In order to prove this exercise, it is equivalent to show that $A = d J$, for some non-negative integer $d$. The only way I am able to think of in order to prove this is via induction but that too I am not able to implement. Removing a vertex from a graph will still give some condition like $A^l = cJ$ is not clear to me.
Thanks in advance!!
Hint: Consider the formula for the number of triangles in a graph, $tr(A^3)/6$. The reason this holds is that, more generally, the entry $i,j$ in $A^k$ is constant (dependent only on $k$) multiple of the number of paths from $i$ to $j$.
When you think about the problem in these terms, you realize it's asking you to assume that every entry of $A^\ell$ is the same, for some $\ell$.
Can you take it from here?