Non-planarity of Markoff graphs \(\mod p\) (Q6204552)

Summary: 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.