  Markoff mod-$p$ graphs are conjectured to be connected for all primes $p$. In
this paper, we use results of Chen and Bourgain, Gamburd, and Sarnak to confirm
the conjecture for all $p > 3.448\cdot10^{392}$. We also provide a method that
quickly verifies connectivity for many primes below this bound. In our study of
Markoff mod-$p$ graphs we introduce the notion of \emph{maximal divisors} of a
number. We prove sharp asymptotic and explicit upper bounds on the number of
maximal divisors, which ultimately improves the Markoff graph $p$-bound by
roughly 140 orders of magnitude as compared with an approach using all
divisors.
