Find the smallest number of edges that a 3-regular graph of girth 4 can have I know the girth of a graph $G$ is the size of a smallest cycle in $G$. I'm trying to find a formula for how many edges in terms of $n$.
I've just been playing around with examples and think a hypercube is a small example that works, but there may be others. $Q_3$ has $2^3=8$ vertices and $3\cdot3^{3-1}=12$ edges. I just struggle with how to add the minimum number of edges to keep it 3-regular while avoiding 3-cycles.

The graph is already given as 3-regular. Therefore the number of edges it has is $\frac32$ times its number of vertices, and we can focus on minimising the vertex count.

Can a 3-regular graph on six vertices (and thus nine edges) have girth 4?

Yes. The complete bipartite graph $K_{3,3}$ is the single such graph up to isomorphism.

What about four vertices (and six edges)?

No. The only such graph is the tetrahedral graph, but it has girth 3.
Thus a 3-regular graph of girth 4 can have at least nine edges.
