A $k$-regular Graph with girth(G) = g has at least f(k,g) vertices I absolutely have no idea on how to prove this so any help is welcome.
Let G be a $k$-regular Graph with girth(G) = g. Then G has at least $f(k,g)$ vertices $(k \geq 3, g \geq 3)$ where
$$f(k,g) := \begin{cases} \frac{k(k-1)^r-2}{k-2} \quad \text{if g=2r+1} \\ \frac{2(k-1)^r -2}{k-2} \quad \text{if g=2r}\end{cases}$$
 A: Have you ever heard of the family tree paradox?
It goes like this: you have two parents. Each of them has two parents, so you have four grandparents. Similarly, you have eight great-grandparents, sixteen great-great-grandparents, and so on: $2^k$ ancestors from $k$ generations ago. A thousand years ago is about thirty generations, so in the year 1017 you had about $2^{30} = 1\,073\,741\,824$ living ancestors. But that's way more than the number of people alive in the world at that time. What gives?
The problem is called pedigree collapse: embarrassingly, if you go far enough back in the family tree, your relationship to your ancestors stops being unique. Maybe your mother's father's father's mother's father's mother is the same person as your father's mother's father's mother's father's mother's father. In graph-theoretic terms, your family tree contains a cycle.
If your family tree has girth $g$, there is a lower bound (in terms of $g$) on how far away that cycle can be. For example, girth $7$ implies that two people with the same grandparent shouldn't have children together: otherwise, one of those children would have two paths up to that shared grandparent, which is a cycle of length $6$. So if your family tree has girth $g \ge 7$, then all $8$ of your great-grandparents are distinct. Counting yourself and everyone up to your grandparents, there are at least $1 + 2 + 4 + 8 = 15$ people in your family tree.
Similarly, if you are in a $d$-regular graph and you build the breadth-first-search tree from one of the vertices, it should have $1 + d + d(d-1) + d(d-1)^2 + \dotsb$ distinct vertices in it, until graph-theoretic pedigree collapse kicks in. A lower bound on girth will tell you that up until a certain point, all of those vertices are distinct, giving you a lower bound on the number of vertices in the graph.
