What question did this study set out to answer?

To establish a lower bound for the circumference of a graph based on its girth and edge count.

April 4, 2026Open Access

Maximal cycles in graphs of large girth

Key Points

To establish a lower bound for the circumference of a graph based on its girth and edge count.
Develop mathematical bounds for graph circumference based on girth and edge relationships.
Examine the case for 2-edge-connected weighted graphs specifically when girth is 4.
Characterize the extremal conditions for the main results.
Demonstrates a cycle length of at least (g - 2)m/(n - 2) for graphs with girth at least g.
For graphs with girth of 4, analogous results confirm the findings for weighted graphs.
Identifies conditions for extremal cases relevant to defined bounds.

Abstract

In this paper we give a lower bound of the circumference of a graph in terms of girth and the number of edges.It is shown that a graph of girth at least g 4 with n vertices and at least m n edges contains a cycle of length at least (g -2)m/(n -2).In particular, for the case g = 4, an analogous result for 2-edge-connected weighted graphs is given.Moreover, the extremal case is characterized in both results.

Bookmark

View Full Paper