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 cube, $Q_3,$ already has three edges at each vertex, so it seems not possible to add in another edge and keep it $3$-regular. – coffeemath Dec 8 '17 at 1:55

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.

• Does this mean that $K_{3,3}$ is the only 1 graph with this property? Or can you make bigger ones with more vertices? I don't quite see if it generalizes – SleekPanther Dec 8 '17 at 3:04
• @SleekPanther Did you notice that the question asked for the smallest number of edges? Furthermore, for regular graphs of a given degree, given either the vertex count or the edge count, the other is determined. So for nine edges, a 3-regular graph must have six vertices. There is nothing more than that. – Parcly Taxel Dec 8 '17 at 3:09