I only have a rough idea, which I would like to have some comments on.
Assume $d \geq 3$. Let $v$ be a vertex of $G$. We observe that any path starting from $v$ must have its ending vertex being part of a cycle, since otherwise some vertex would have degree $1$.
Amongst the graph with such property, the ones with the least vertices are those where the paths from $v$ "pair up" nicely, i.e. we avoid creating new cycles if possible. Call the paths $p_1, p_2$, and the cycle created this way $\gamma$.
Since deg$(v) \geq $3, at least another path $p_3$ starting from $v$ exists, which would have to be adjoined as well. Again, the graphs with the least vertices would be ones where this path joins up with an existing cycle. Here we observe that either $p_1$ or $p_3$ must have length at least $\lfloor \frac{g-1}{2} \rfloor$, since otherwise we would have a cycle of length less than $g$.
Please refer to the following picture for illustration.
Wlog assume $p_1$ is of this length. Now let $w$ be a neighbor of $v$ on $p_1$. The same analysis applies with $w$, and we have a path starting from $w$ that otherwise does not intersect $p_1$. Let $z$ be the neighbor of $w$ on this path. Then the edge $wz$, together with the edge $vw$, is a path starting from $v$. So it must also reach the required length of $\lfloor \frac{g-1}{2} \rfloor$ (at which point presumably it will join up with another path from $v$ to create a cycle). Since at each vertex on this new path (e.g. $w$, $z$), the graph must split into at least $d$ different branches, we have $n \geq c \cdot d^k, \text{where } k = \lfloor \frac{g-1}{2} \rfloor$ and $c > 0$.
Now I have some questions:
- I'm not very confident about this proof since it doesn't say much about the paths starting from vertices other than $v$. Presumably they will all pair up nicely, but I can't check that. And if this is true then wouldn't the bound we have here be a very weak one?
- Another point is that my proof is about a very specific construction, which I'm not sure is in the spirit of the question.
- I added the constant $c$ above to account for the extra vertices not in the formula (e.g. $v$, or the vertices on $p_2$). But it seems this $c$ counts more than just those vertices? Please elaborate on this point if possible.
