Circumference, Minimum Degree and Clique Number

Abstract

The circumference and the clique number of a graph is the length of a longest cycle and the largest order of a clique in it respectively. We show that the circumference of a 2-connected non-Hamiltonian graph $G$ is at least the sum of its clique number and minimum degree unless $G$ is one of two specific graphs.