  For a finite graph $G=(V,E)$ let $G^*$ be obtained by considering a random
perfect matching of $V$ and adding the corresponding edges to $G$ with weight
$\varepsilon$, while assigning weight 1 to the original edges of $G$. We
consider whether for a sequence $(G_n)$ of graphs with bounded degrees and
corresponding weights $(\varepsilon_n)$, the (weighted) random walk on
$(G_n^*)$ has cutoff. For graphs with polynomial growth we show that
$\log\left(\frac{1}{\varepsilon_n}\right)\ll\log|V_n|$ is a sufficient
condition for cutoff. Under the additional assumption of vertex-transitivity we
establish that this condition is also necessary. For graphs where the entropy
of the simple random walk grows linearly up to some time of order $\log|V_n|$
we show that $\frac{1}{\varepsilon_n}\ll\log|V_n|$ is sufficient for cutoff. In
case of expander graphs we also provide a complete picture for the
complementary regime $\frac{1}{\varepsilon_n}\gtrsim\log|V_n|$.
