  Aldous and Fill conjectured that the maximum relaxation time for the random
walk on a connected regular graph with $n$ vertices is $(1+o(1))
\frac{3n^2}{2\pi^2}$. This conjecture can be rephrased in terms of the spectral
gap as follows: the spectral gap (algebraic connectivity) of a connected
$k$-regular graph on $n$ vertices is at least $(1+o(1))\frac{2k\pi^2}{3n^2}$,
and the bound is attained for at least one value of $k$. Based upon previous
work of Brand, Guiduli, and Imrich, we prove this conjecture for cubic graphs.
We also investigate the structure of quartic (i.e. 4-regular) graphs with the
minimum spectral gap among all connected quartic graphs. We show that they must
have a path-like structure built from specific blocks.
