Maximum Girth-to-Diameter Ratio

Definitions and mathematical statement

The source asks about graphs of minimum vertex degree at least $3$, but does not explicitly specify finiteness, connectedness, simplicity, or whether edges are undirected. The following precise formulation is conditional on the intended class being finite, connected, simple, undirected graphs; this convention requires confirmation from the source.

Let $\mathcal G$ denote that class subject to $\delta(G)\geq 3$, where $\delta(G)=\min_{v\in V(G)}\deg_G(v)$. For $G\in\mathcal G$, define $d_G(u,v)$ as the minimum number of edges in a path joining $u$ and $v$, and set \[ \operatorname{diam}(G)=\max_{u,v\in V(G)}d_G(u,v). \] Define $\operatorname{girth}(G)$ as the minimum number of edges in a cycle of $G$. Under the stated conditional conventions, these quantities are finite and the diameter is positive.

Determine \[ x=\lim_{D\to\infty}\sup\left\{\frac{\operatorname{girth}(G)}{\operatorname{diam}(G)}:G\in\mathcal G,\ \operatorname{diam}(G)\geq D\right\}. \] In particular, is $x>1$? Equivalently, does there exist $\varepsilon>0$ such that for every $D\in{\mathbb{N}}$ there exists $G\in\mathcal G$ satisfying \[ \operatorname{diam}(G)\geq D, \qquad \operatorname{girth}(G)>(1+\varepsilon)\operatorname{diam}(G)? \]

The supplied background also asks whether girth minus diameter is unbounded. Under the same conditional graph conventions, this asks whether \[ \forall M\in{\mathbb{R}}\ \exists G\in\mathcal G: \operatorname{girth}(G)-\operatorname{diam}(G)>M. \] The background describes this as a "stronger question," but does not specify the comparison intended; that description is retained as source wording rather than an asserted logical relationship.

Short English statement

Determine the asymptotic largest ratio of girth to diameter among graphs with minimum degree at least $3$, and decide whether that ratio exceeds $1$. The supplied background additionally asks whether girth minus diameter is unbounded. The precise graph conventions remain to be confirmed.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30003134$, titled Maximum Girth-to-Diameter Ratio, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record lists proposed year $2016$ and does not identify a proposer.
• Supplied report citation: Combinatorics and Probability (2017), Oberwolfach Reports, DOI 10.4171/owr/2016/22, pp. 1189--1257. https://doi.org/10.4171/owr/2016/22. The background describes this collection as drawn from workshop reports and their open-problem discussions. The supplied citation's year $2017$ differs from the proposed year and the year appearing in the DOI; these details are preserved without reconciliation.
• Supplied literature reference: Linial, Girth versus Diameter of Graphs. https://ems.press/content/serial-article-files/46798.
• Supplied literature reference: Linial and Simkin, A Randomized Construction of High-Girth Regular Graphs. https://arxiv.org/abs/1911.09640.
• Supplied literature assessment, checked 2026-08-21: the record labels the problem open, reports that the limsup is only known to lie between $1$ and $2$, and reports that unboundedness of girth minus diameter is unresolved. This is supplied dated curation derived from the OWR collection, not an independently verified literature assessment. Its time-sensitive status and cited claims require independent verification.
• The registry labels the statement corrected_verified and reports manual semantic, typographic, and LaTeX review. These are supplied registry qualifications, not independent verification of the formulation or mathematical status in this draft.