  Edge-girth-regular graphs (abbreviated as $egr$ graphs) are a class of highly
regular graphs. More specifically, for integers $v$, $k$, $g$ and $\lambda$ an
$egr(v,k,g,\lambda)$ graph is a $k$-regular graph with girth $g$ on $v$
vertices such that every edge is contained in exactly $\lambda$ cycles of
length $g$. The central problem in this paper is determining $n(k,g,\lambda)$,
which is defined as the smallest integer $v$ such that an $egr(v,k,g,\lambda)$
graph exists (or $\infty$ if no such graph exists) as well as determining the
corresponding extremal graphs. We propose a linear time algorithm for computing
how often an edge is contained in a cycle of length $g$, given a graph with
girth $g$. We use this as one of the building blocks to propose another
algorithm that can exhaustively generate all $egr(v,k,g,\lambda)$ graphs for
fixed parameters $v, k, g$ and $\lambda$. We implement this algorithm and use
it in a large-scale computation to obtain several new extremal graphs and
improvements for lower and upper bounds from the literature for
$n(k,g,\lambda)$. Among others, we show that $n(3,6,2)=24, n(3,8,8)=40,
n(3,9,6)=60, n(3,9,8)=60, n(4,5,1)=30, n(4,6,9)=35, n(6,5,20)=42$ and we
disprove a conjecture made by Araujo-Pardo and Leemans [Discrete Math.
345(10):112991 (2022)] for the cubic girth 8 and girth 12 cases. Based on our
computations, we conjecture that
$n(3,7,6)=n(3,8,10)=n(3,8,12)=n(3,8,14)=\infty.$
