Unbounded Girth Minus Diameter at Minimum Degree Three

Definitions and mathematical statement

The source asks whether girth minus diameter is unbounded for graphs in which every vertex has degree at least three. It does not explicitly specify finiteness, simplicity, or connectedness. The following precise formulation uses the finite, simple, undirected, connected interpretation; these graph conventions require confirmation against the source.

Let $G=(V,E)$ be a finite, simple, undirected, connected graph. For $v\in V$, let $\deg_G(v)$ be the number of its neighbors, and define the minimum degree by \[ \delta(G)=\min_{v\in V}\deg_G(v). \] For vertices $u,v\in V$, let $d_G(u,v)$ be the minimum number of edges in a path joining them. Define \[ \operatorname{diam}(G)=\max_{u,v\in V}d_G(u,v). \] The girth $\operatorname{girth}(G)$ is the minimum number of edges in a cycle of $G$. Every finite graph with minimum degree at least three contains a cycle, so its girth is defined and finite.

Under the stated interpretation, the question is whether \[ \forall M\in{\mathbb{Z}}_{\ge 0}\quad \exists\,G\text{ finite, simple, undirected, and connected}: \qquad \delta(G)\ge 3 \quad\text{and}\quad \operatorname{girth}(G)-\operatorname{diam}(G)\ge M. \] The source does not supply conventions for disconnected or infinite graphs, or for graphs with loops or parallel edges; the displayed formulation is conditional on the graph conventions above.

Short English statement

Can the length of a shortest cycle exceed the largest distance between two vertices by arbitrarily large amounts in graphs whose vertices all have degree at least three? The displayed formulation interprets the graphs as finite, simple, undirected, and connected; the supplied record does not explicitly state these conventions.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30004356$, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record supplies proposed year $2020$ and names no individual proposer.
• Supplied source citation: Combinatorics (2021), Oberwolfach Reports, DOI 10.4171/owr/2020/1, pp. 6--89. Source URL and literature-source label "OWR report": https://doi.org/10.4171/owr/2020/1. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's year is retained as supplied.
• Supplied literature source: "Linial--Simkin, high-girth regular graphs," https://doi.org/10.1002/rsa.20976.
• Literature assessment checked at 2026-08-22: the supplied curation labels the problem open and states that graphs of minimum degree at least three with unbounded girth minus diameter remain unknown, and that high-girth regular graph constructions do not settle this trade-off. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says its mathematical content was preserved while notation, typography, omitted definitions, or duplicate clauses were repaired. This is a supplied editorial label, not independent mathematical verification of this draft.