\deg(v)\}.$$ We then simply choose a *pairing* $\pi$ on ${\ensuremath{\mathcal{X}}}$ (i.e., an involution without fixed points), and interpret every pair of matched half-edges $\{x,\pi(x)\}$ as an edge between the corresponding vertices. Loops and multiple edges are allowed.

The *non-backtracking random walk* (<span style="font-variant:small-caps;">nbrw</span>) on the graph $G=G(\pi)$ is a discrete-time Markov chain with state space ${\ensuremath{\mathcal{X}}}$ and transition matrix $$P(x,y)=
\left\{
\begin{array}{ll}
\frac{1}{\deg(\pi(x))} & \textrm{ if y is a neighbour of } \pi(x) \\
0 & \textrm{ otherwise}.
\end{array}
\right.$$ In this definition and throughout the paper, two half-edges $x=(u,i)$ and $y=(v,j)$ are called *neighbours* if $u=v$ and $i\neq j$, and we let $\deg(x):=\deg(u)-1$ denote the number of neighbours of the half-edge $x=(u,i)$. In words, the chain moves at every step from the current state $x$ to a uniformly chosen neighbour of $\pi(x)$.

Note that the matrix $P$ is symmetric with respect to $\pi$: for all $x,y\in{\ensuremath{\mathcal{X}}}$, $$\begin{aligned}
\label{sym}
P(\pi(y),\pi(x))=P(x,y).\end{aligned}$$ In particular, $P$ is doubly stochastic: the uniform law on ${\ensuremath{\mathcal{X}}}$ is invariant for the chain. The *worst-case total-variation distance to equilibrium* at time $t\in{\ensuremath{\mathbb{N}}}$ is $$\begin{aligned}
\label{cd}
{\ensuremath{\mathcal{D}}}(t)  & := & \max_{x\in{\ensuremath{\mathcal{X}}}}\left\{\frac{1}{2}\sum_{y\in{\ensuremath{\mathcal{X}}}}\left|P^t(x,y)-\frac{1}{N}\right|\right\}.\end{aligned}$$ ${\ensuremath{\mathcal{D}}}$ is non-increasing, and the number of transitions that have to be made before it falls below 