For $d \geq 3$ (degree) and $r \geq 3$ (radius), say that a $d$-regular (finite, simple, non-oriented) graph $G$ is $r$-almost-tree if it contains no cycle of length $\leq 2 r$: in other words, we want our graph to look locally like a $d$-regular tree, in the sense that its restriction to any ball of radius $r$ always has exactly the (local) structure of a $d$-regular tree. Denote by $N(d, r)$ the minimum possible of vertices for a $r$-almost-tree $d$-regular graph. What can one tell about $N(d, r)$?


A first observation is that $N(d, r)$ is always finite. [Proof: For $n$ large, consider $d$ random involutions without fixed point of $\mathfrak{S}\_{2 n}$; then the Cayley graph of the subgroup that they generate will be $r$-almost-tree with a probability tending to $1$ as $n \to \infty$]. But what about sharp upper bounds? In particular, a trivial lower bound on $N(d, r)$ is given by the size of a ball of radius $d$ in a tree, i.e. $1 + d + (d - 1) d + \cdots + (d - 1)^{r - 1} d =: N\_0(d, r)$. In view of this, two natural questions are the following:


* In which cases does one have $N(d, r) = N\_0(d, r)$? In particular, for fixed $d$, are there intinitely many $r$'s such that $N(d, r) = N\_0(d, r)$? (Note: I investigated the case $d = 3$: then $r = 1$ and $r = 2$ fit, but not $r = 3$ nor $r = 4$).
* For fixed $d$, is the ratio $N(d, r) / N\_0(d, r)$ bounded as $r$ tends to infinity?…



Minimum size of regular graph with no short cycles
The problem of determining the smallest regular graphs with degree $k$ and girth $g$ is normally known as the cage problem.


It has a large literature which is nicely summarised in the Dynamic Cage Survey in the Electronic Journal of Combinatorics.


<https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS16/pdf/>


(Apparently this is about to be updated)


