# software graph theory for finding graph with girth 3

Is there any software for finding all graphs (edges and nodes) with girth(the girth of a graph is the length of a shortest cycle contained in the graph) three and diameter at least three?

The eccentricity of a vertex v is the greatest distance between v and any other vertex.

The diameter d of a graph is the maximum eccentricity of any vertex in the graph.

• As far as finding every graph satisfying your conditions, this would be impossible, since there're clearly infinitely many (consider the family of "extended paws" formed by lengthening the extra (non-$K_3$) edge in the paw into an arbitrarily long path). I don't think there'd be a concise way to describe all infinite families with your properties, either. I think you'd have an easier time thinking about graphs not in your class, i.e. those with girth $\geq 4$ and diameter $\leq 2$. This will still be infinite (all complete bipartite graphs are in it, for instance), but more well-behaved. Commented May 30, 2020 at 21:35

You can use nAUTy and tools for this:

./geng -cq 7 | ./countg -g3 -Z3:

This is using geng to generating all connected graphs on 7 vertices and filtering using countg all those with girth 3 (-g3) and diameter at least 3 (-Z3:).

To give an idea of how many there are, here is a table for n = 5 to 10:

n   matches  total
5       3       21
6      37      112
7     426      853
8    6705    11117
9  168197   261080
10 7589873 11716571

So there are only 426 graphs on 7 vertices out of 853 total, but 7,589,873 on 10 vertices.