On the Realizability of Edge-Girth Sequences

Abstract

The edge-girth of an edge \(e\) in a simple connected graph is the length of a shortest cycle containing \(e\), with \(g_e = \infty\) if no such cycle exists, and the edge-girth sequence of a graph is the nondecreasing sequence of the edge-girths of its edges. We characterize the sequences that are realizable as the edge-girth sequence of a simple connected graph. A constant sequence \((g^{(m)})\) with \(g\) finite and \(m \geq 1\) is realizable if and only if \(m = g\) or \(m \geq \lceil 3g/2 \rceil\). Otherwise, writing \(S = S_0 \uplus (g^{(m)})\), where \(g\) is the maximum value of \(S\) and \(m\) its multiplicity, we prove that \(S\) is realizable if and only if \(S_0\) is realizable and \(m\) lies in an explicit set determined by \(g\) and by the maximum diameters of the graphs realizing \(S_0\), alone or extended by fewer than \(g\) edges of edge-girth \(g\). The proof rests on a chaining lemma, which turns a shortest cycle of a realization into a lower bound on the maximum diameter of the realizations of a shorter sequence.

Citation

Lilian Marey, Paul Hilaire, Charlotte Laclau. On the Realizability of Edge-Girth Sequences. Preprint, arXiv:2607.25629, 2026.