The graph circumference is the length of any longest cycle in a graph. Hamiltonian
graphs on 
vertices therefore have circumference of 
.
For a cyclic graph 
, the graph circumference is the polynomial
degree of the cycle polynomial 
.
For a cyclic graph, the maximum element 
of the detour matrix
over all adjacent vertices 
is one smaller than the circumference.
The graph circumference of a self-complementary graph is either 
(i.e., the graph is Hamiltonian),
,
or 
(Furrigia 1999, p. 51).
Ma and Zhao (2026) proved that every finite connected vertex-transitive graph on 
vertices has circumference
at least 
for an absolute constant 
. For all sufficiently large vertex
degrees 
,
the lower bound is 
.
These results give progress toward the Lovász
conjecture without establishing Hamiltonicity.
Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.
-
for 
-
-
-
