Cycles on a discrete torus 
Consider an $m\times n$ grid graph whose opposing vertices are connected (i.e. the graph is a discrete torus). How many distinct cycles are there?

I know that for the case of $1\times n$ or $n\times 1$, there are $1+n$ distinct cycles (one of length $n$, and $n$ of length $1$). I planned on brute-forcing a few cases to see if I could identify some kind of pattern. However, I feel like a combinatorial approach would be more effective. I don't know what to do from here to get a general formula.
 A: For the $2 \times n$ torus we can find an exact formula: there are $3^n + (-1)^n + 4n^2 - 3n$ cycles. These come in three types:

*

*Cycles that go the long way around the torus. Say that they have $k$ vertical steps for some even $k$; there's $\binom nk$ ways to choose the locations of the vertical steps, $2^k$ ways to choose whether they go up or down, and then $2$ ways to pick the horizontal steps that complete the cycle (for one vertical step, you pick whether you go left from its top or bottom vertex, and that determines the rest). So the total is $$2 \sum_{k \text{ even}}\binom nk 2^k = \sum_{k=0}^n \binom nk (2^k + (-2)^k) = 3^n + (-1)^n.$$

*Cycles that don't go all the way around the torus, but start and end at different columns. There's $\binom n2$ ways to choose the columns, $2^2$ ways to choose the edge used in each column, and $2$ ways to decide if we go left or right from one column to reach the other, for $4n(n-1)$ total.

*Finally, there's $n$ cycles of length $2$.


Now that I've actually proved something, I can go ahead and say that we probably can't prove anything else. Even for the $3\times n$ torus, I expect that any formula will be much more complicated because there's so many more different types of cycles to consider, and they can double back on themselves in many more different ways.
I used Mathematica to find the answer for small $(m,n)$:
\begin{array}{c|ccccc}    m\backslash n & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 2 & 3 & 4 & 5 & 6 \\     2 & 3 & 20 & 53 & 134 & 327\\     3 & 4 & 53 & 312 & 1531 & 7298\\     4 & 5 & 134 & 1531 & 14704 & 132089\\     5 & 6 & 327 & 7298 & 132089 & 2183490  \end{array}
Here's my Mathematica code, cleaned up a bit:
torusGraph[m_,n_]:=Graph[Flatten[Table[{{a,b}<->{Mod[a+1,m,1],b}, 
  {a,b}<->{a,Mod[b+1,n,1]}},{a,m},{b,n}]]]
cycleCount[m_,n_]:=Length[FindCycle[torusGraph[m,n],{1,Infinity},All]]

cycleCount only works properly for $m,n \ge 3$, since otherwise we get a multigraph and Mathematica is not consistent about distinguishing cycles with the same vertex sequence. Fortunately, we have a formula for the other cases.
Sequence A231829 on the OEIS gives a table of the cycle counts for a grid graph, which is the version of this problem that doesn't wrap around. Here, no general formula is known either: for the $1 \times n$ grid graph (not included in OEIS's table) the number is always $0$, for $2\times n$ it is $\binom n2$, for $3\times n$ it is A059020 and has at least a known recurrence relation, and after that even the recurrence relation is only empirical.
