Number of Closed Walks of Length 2k I have often seen that
$$
\hom(C_{2k},G) = [\text{\# of closed walks in $G$ of length $2k$}]. \qquad \qquad (\ast)
$$
Below is my attempt at a start of a proof:
Let $\text{Hom}(C_{2k},H)$ be the set of
all homomorphisms from $C_{2k}$ to $H$ and let
$W_{2k}$ be the set of all closed walks of length
$2k$ in $H$. Let $V(C_{2k}) = \{v_1,...,v_{2k}\}$.
Observe that
$$
W_{2k} = \{ (w_1,...,w_{2k}) \ 
| \ w_{i}w_{i+1} \in E(H)\} \qquad  (\text{indices are taken modulo $2k$}).
$$
Note that the above tuples are ordered $2k$-tuples.
Now observe that if $\phi \in \text{Hom}(C_{2k},H)$ then
$$
\big(\phi(v_1),...,\phi(v_{2k})\big), \big(\phi(v_2),...,\phi(v_{2k}),\phi(v_1)\big),...,
\big(\phi(v_{2k}),\phi(v_1),...,\phi(v_{2k-1})\big) \in W_{2k}
$$
However, I am a bit stuck as this means that every homomorphism corresponds with at least $2k$ closed walks in $G$. Moreover, I think one can prove that every closed walk in $G$ corresponds with at least $2k$ homomorphisms:
Proof.
Let $H$ be a graph with a closed walk of length
$2k$:
$$
w_1e_1w_2e_2w_3,...,w_{2k}e_{2k}w_1
$$
where the $w_i$ and $e_i$ are
not necessarily distinct. Let
$V(C_{2k}) = \{v_1,...,v_{2k}\}$ and define
$\phi_m$ by setting $\phi_m(v_i) = w_{i+m}$ where
indices are taken modulo $2k$. Then
for any $v_jv_{j+1} \in C_{2k}$ we have that
$\phi_m(v_j)\phi_m(v_{j+1}) = w_{j+m}w_{j+m+1} = e_{j+m} \in E(H)$.
There are at least $2k$ choices for $m$ modulo $2k$ giving us
our result.
I am a bit confused as to how to complete the proof of $(\ast)$. I might be making an error in my above reasoning. Any advice or hints on how to fix this argument would be much appreciated.
Thanks in advance for your time.
 A: It is true that having a single homomorphism $\phi\colon C_{2k} \to H$ lets you deduce the existence of $2k$ closed walks of length $2k$ in $H$, and having a single closed walk of length $2k$ lets you deduce the existence of $2k$ homomorphisms. (The $2k$ closed walks/homomorphisms may not all be distinct, but that is a different matter.)
But to prove that the number of homomorphisms is equal to the number of closed walks, it doesn't matter how many homomorphisms are vaguely related to each closed walk, and vice versa. What we need to do is define a bijection $F \colon \text{Hom}(C_{2k},H) \to W_{2k}$, and check that it's a bijection. A bijection can only exist between two sets of equal cardinality, so we would conclude that $|\text{Hom}(C_{2k},H)| = |W_{2k}|$.
One way to define this bijection is to say that for every $\phi \in \text{Hom}(C_{2k},H)$, $F(\phi)$ is the closed walk that visits $\phi(v_1), \phi(v_2), \dots, \phi(v_{2k}), \phi(v_1)$ in that order. We should prove:

*

*This actually gives a closed walk - all the edges we want are there.

*$F$ is surjective: every possible closed walk comes from some homomorphism $\phi$.

*$F$ is injective: if $\phi_1, \phi_2$ give the same closed walk, then they're equal as homomorphisms.

It doesn't matter that knowing the existence of the homomorphism $\phi$ tells us about other closed walks in the graph - at most, that tells us that we could have defined $F$ differently.
