$k$ steps.

We begin with a formula for the complexity of finite graphs.

p.finite Suppose that $\gh$ is a finite connected graph. Then $$\log \cp(\gh) 
=
-\log (2|\edges(\gh)|) + \sum_{x \in \verts(\gh)} \log \deg_\gh(x)
- \sum_{k \ge 1} 
{1 \over k} \left(\sum_{x \in \verts(\gh)} p_k(x;\gh) - 1 \right)
\,.$$

Let $P$ be the transition matrix for simple random walk on $\gh$ and $I$ be the identity matrix of the same size. As shown by \[b\].RungeSachs/, we may rewrite \[e\].MTT/ as $$\cp(\gh) = {\prod_{x \in \verts(\gh)} \deg_\gh(x) \over \sum_{x \in
\verts(\gh)} \deg_\gh(x)} \detp (I-P)
%\cp(\gh) = {\prod_{x \in \verts(\gh)} \deg_\gh(x) \over |\vertex(\gh)| }
%\detp [I-P]$$ \[the proof follows from looking at the coefficient of $t$ in $\det\big(I-P-t I\big) = (\det D_\gh)^{-1} \det\big(\Delta_\gh - t
D_\gh\big)$ and using the Matrix-Tree Theorem in its original form with cofactors\]. Since the sum of the degrees of a graph equals twice the number of its edges, we obtain $$\log \cp(\gh)
= 
-\log (2|\edges(\gh)|) + \sum_{x \in \verts(\gh)} \log \deg_\gh(x)
%-\log |\vertex(\gh)| + \sum_{x \in \verts(\gh)} \log \deg_\gh(x)
+ \log \detp (I-P)
\,.
\label e.mtt'$$ Let $\Lambda$ be the multiset of eigenvalues of $P$ other than 1 (with multiplicities). Since $\Lambda \subset \CO{-1, 1}$, we may 