Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin?
Or putting it differently: What is "Pólya's Random Walk Constant" on such graphs?
I think what I was looking for is simply the diagonal entries of the $N$-th power of the adjacence matrix for the given graph. Maybe I should have noted that I'm dealing with finite graphs and I'm not expert enough to see if Pólya's Random Walk Constant makes sense here.