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.

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – SleekPanther Dec 8 '17 at 3:04
  • $\begingroup$ @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. $\endgroup$ – Parcly Taxel Dec 8 '17 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.