On the maximal distance between triangular embeddings of a complete graph

The distance d(f,f′) between two triangular embeddings f and f′ of a complete graph is the minimal number t such that we can replace t faces in f by t new faces to obtain a triangular embedding isomorphic to f′. We consider the problem of determining the maximum value of d(f,f′) as f and f′ range over all triangular embeddings of a complete graph. The following theorem is proved: for every integer s⩾9, if 4s+1 is prime and 2 is a primitive root modulo (4s+1), then there are nonorientable triangular embeddings f and f′ of K12s+4 such that d(f,f′)⩾(1/2)(4s+1)(12s+4)-O(s), where (4s+1)(12s+4) is the number of faces in a triangular embedding of K12s+4. Some number-theoretical arguments are advanced that there may be an infinite number of odd integers s satisfying the hypothesis of the theorem.