Edge condition for hamiltonicity in balanced tripartite graphs

Abstract

A well-known theorem of Entringer and Schmeichel asserts that a balanced bipartite graph of order $2n$ obtained from the complete balanced bipartite $K_{n,n}$ by removing at most $n - 2$ edges, is bipancyclic. We prove an analogous result for balanced tripartite graphs: If $G$ is a balanced tripartite graph of order $3n$ and size at least $3n^{2} - 2n + 2$, then $G$ contains cycles of all lengths.