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.

Keywords

• Hamilton cycle
• pancyclicity
• tripartite graph
• edge condition