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.



Do graphs with an odd number of walks of length $\ell$ between any two vertices exist?
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.


