Do graphs with an odd number of walks of length $\ell$ between any two vertices exist? Given $\ell\ge 1$, we say a graph $G$ is $\ell$-good if for each $u,v\in G$ (not necessarily distinct), the number of walks of length $\ell$ from $u$ to $v$ is odd. We say a graph $G$ is good if it is $\ell$-good for some $\ell\ge 1$.
Do good graphs exist? For clarity, I am only talking about simple graphs (which lack loops and multiple edges).
Context: In Stanley’s book on Algebraic combinatorics, Exercise 1.13 is about proving an interesting property held for all good graphs. A friend of mine told me that after solving the exercise, he realized he didn’t know of any example of such graphs. I too am stumped about whether such graphs can exist.
A computer search revealed that none exist with $7$ or fewer vertices. I am unclear about the specifics of the search, they were done by my friend.
 A: Here is a combinatorial argument; surely, it can also be rewritten in  an algebraic way using the adjacency matrices.
As usual, $N(v)$ denotes the set of vertices adjacent with $v$. We also denote by $f_n(u,v)$ the number of length $n$ walks from $u$ to $v$. Notice that
$$
  f_{n+1}(u,v)=\sum_{w\in N(v)} f_n(u,w). \qquad(*)
$$
Suppose that $f_\ell(u,v)\equiv 1$ for all $u$ and $v$ (all congruences are modulo $2$). By $(*)$, we have $\deg u\equiv f_{\ell+1}(u,v)\equiv \deg v$. Hence all degrees are of the same parity.
Case 1. Assume that all degrees are odd (so the number of vertices is even). By $(*)$ we then get $f_{\ell+1}(u,v)\equiv 1$. Similarly, $1=f_{\ell+1}(u,v)=f_{\ell+2}(u,v)=\dots=f_{2\ell}(u,v)$.
On the other hand, considering in each length $2\ell$ path the middle vertex $w$, we get
$$
  f_{2\ell}(u,v)=\sum_w f_\ell(u,w)f_\ell(w,v)\equiv \sum_w1\equiv 0,
$$
since the number of vertices is even. A contradiction.
Case 2. Assume that all degrees are even. Then we repeat @TimothyChow's argument from the previous answer. For completeness: We consider an involution on the set of walks from $u$ to $u$ consisting in reverting the path.  It provides $f_\ell(v,v)\equiv 0$ if $\ell$ is odd (so this case is ruled out), and $f_\ell(v,v)\equiv \sum_u f_{\ell/2}(v,u)$ otherwise. But all length $\ell/2$ walks from $v$ can be split intpo groups differing only by the last step, and each group comtains an even number pf walks. Hence $f_\ell(v,v)\equiv 0$ in this case as well.
A: A graph without loops cannot be good.
Assume the contrary, let $G$ have $n$ vertices and be good.
Let $A$ be the adjacency matrix of $G$, let $\lambda_1,\ldots,\lambda_n$ be its eigenvalues over some extension of $\mathbb{F}_2$. We have $\sum_{i=1}^n \lambda_i=\mathrm{tr} A=0$.
That $A$ is good means that $A^\ell$ is an all-1 matrix over $\mathbb{F}_2$. It has rank 1, thus at least $n-1$ eigenvalues of $A^\ell$ are 0. On the other hand, the eigenvalues of $A^\ell$ are $\lambda_1^\ell,\ldots,\lambda_n^\ell$. Therefore, at least $n-1$ $\lambda_i$'s are zero, and, since $\sum \lambda_i =0$, all $\lambda_i$'s are 0. Thus $A$ is nilpotent. Since $A^\ell$ has rank 1, we get $A^{\ell+1}=0$ (indeed, denote $\mathrm{im} A^{\ell}:=X$, then $\dim X=1$. We have $\mathrm{im} A^{\ell+1}\subset \mathrm{im} A^{\ell}=X$, and also $\mathrm{im} A^{\ell+1}=AX$. Since $\dim X=1$, either $\mathrm{im} A^{\ell+1}=\{0\}$, or $AX=\mathrm{im} A^{\ell+1}=X$; in the latter case $A$ is not nilpotent since $A^kX=X\ne \{0\}$ for all $k=0,1,2,\ldots$). So, $A\cdot A^\ell=0$, that means that the sum of entries in every row of $A$ is even, i.e., every vertex in $G$ must have even degree.
Now pick a vertex $v$ and let $W$ be the set of all walks of length $\ell$ from $v$ to $v$. The cardinality of $W$ is odd by hypothesis. The operation $\rho$ of reversing a walk is an involution on $W$, so the number of fixed points of $\rho$ is odd; these fixed points consists of walks of the form "take any walk of length $\ell/2$ starting at $v$ and then retrace your steps back to $v$" (so in particular, $\ell$ must be even).  But because every vertex has even degree, in particular there is an even number of choices for the last step of the walk of length $\ell/2$, so the total number of walks of length $\ell/2$ must be even. This is a contradiction.
