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).
Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.
-
for 
-
-
-
Ma and Zhao (2026) proved that every finite connected vertex-transitive graph on 
vertices has circumference
at least 
for an absolute constant 
, a lower bound linear in the number of vertices.
For all sufficiently large vertex degrees 
, the lower bound is 
. These results give progress toward the Lovász
conjecture without establishing Hamiltonicity.
