Non-planarity of Markoff graphs $\mathrm{mod}p$

Abstract

We prove the non-planarity of a family of $3$-regular graphs constructed from the solutions to the Markoff equation $x^2+y^2+z^2=xyz$ modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these graphs. Non-planarity for large primes would follow assuming a spectral gap, which was the original motivation. For primes congruent to $1$ modulo $4$, or congruent to $1$, $2$, or $4$ modulo $7$, explicit constructions give an alternate proof of non-planarity.