On the maximal distance between triangular embeddings of a complete graph. (Q2490841)

The distance \(d(f,f')\) between two triangular imbeddings \(f\) and \(f'\) of a fixed complete graph is the minimum number \(t\) such that one can replace \(t\) faces in \(f\) with \(t\) new faces to obtain a triangular imbedding isomorphic to \(f'\). Of interest is the determination of the maximum value of this distance, as \(f\) and \(f'\) vary over all triangular imbeddings of a fixed complete graph. A simple calculation shows that \(T(s)=(4s+1)(12s+4)\) is the number of faces in a triangular imbedding of \(K_{12s+4}\). The author shows that, if \(s\geq 9\) and \(4s+1\) is prime and 2 is a primitive root modulo \((4s+1)\), then there are nonorientable triangular imbeddings \(f\) and \(f'\) of \(K_{12s+4}\) such that \(d(f,f')\geq (1/2)T(s)-O(s)\).