On the minimal nonzero distance between triangular embeddings of a complete graph Original Research Article

Given two triangular embeddings f and f′ of a complete graph K and given a bijection φ : V(K)→V(K), denote by M(φ) the set of faces (x,y,z) of f such that (φ(x),φ(y),φ(z)) is not a face of f′. The distance between f and f′ is the minimal value of |M(φ)| as φ ranges over all bijections between the vertices of K. We consider the minimal nonzero distance between two triangular embeddings f and f′ of a complete graph. We show that 4 is the minimal nonzero distance in the case when f and f′ are both nonorientable, and that 6 is the minimal nonzero distance in each of the cases when f and f′ are orientable, and when f is orientable and f′ is nonorientable.