Regular Girth Graph

The term regular girth graph is used in this work for a finite simple connected graph that is -regular and has girth , where and are integers. Such a graph is usually called a -graph (Jørgensen 2005). The equivalent notation -graph uses for the common vertex degree. A cage graph has the smallest possible order for the given and . A record -graph is a smallest known example, but a smaller -graph may still exist.

Exoo and Jajcay (2013, pp. 16-28 and 44-47) survey constructions using Cayley graphs, graph covers defined by voltage graphs, finite geometry, and excision, which removes parts of a larger graph and restores regularity. Work on girth 5 includes the algebraic constructions of Jørgensen (2005) and the finite geometry constructions of Abajo et al. (2019).

Exoo et al. (2026) combine exhaustive and heuristic searches with graph constructions. Their companion repository supplies code and graph data for the graph cover and excision methods (AGT-Kulak). Complementary work by de la Cruz and Pizaña (2026) uses symmetry in exhaustive searches to improve lower bounds on the orders of cages.

The following sources document cages or record graphs. The survey and archived tables give dated records, while House of Graphs maintains an updated table and distinguishes proved cages from graphs giving only upper bounds.

The following table lists parameters for selected small graphs documented in these sources. Here , , and are the degree, girth, and order, respectively. The listed orders are realized by constructions, including historical records, and need not be current best upper bounds. Graphs in different graph isomorphism classes may have the same parameters.

			reference
3	13	272	Biggs (1998, p. 21)
3	14	384	Exoo (2002)
3	14	406	Biggs (1998, p. 21)
4	9	270	Exoo et al. (2026)
4	9	275	Exoo and Jajcay (2013)
4	10	320	Exoo et al. (2026)
4	10	384	Exoo and Jajcay (2013)
5	7	152	Royle
8	5	80	Jørgensen (2005)
9	5	96	Jørgensen (2005)
10	5	126	Jørgensen (2005)
11	5	160	Royle
11	6	240	Wong (1986)
12	5	203	Exoo (2004)
13	5	226	Abajo et al. (2019)
13	5	240	Jørgensen (2005)
14	5	280	Abajo et al. (2019)
14	5	312	Royle
15	5	406	Royle
16	5	480	Royle
17	5	576	Royle

For example, Jørgensen (2005) constructed a -graph on 96 vertices. As of Oct. 29, 2026, this remains a smallest known example, while the order of a cage graph satisfies (Exoo and Jajcay 2013, p. 36; House of Graphs). Thus 86 is a lower bound, not the order of a known example.

The 96-vertex construction uses two sets of vertices, and , indexed by the cyclic group . Let

The 42 differences with distinct run through the elements outside the subgroup exactly once, with arithmetic performed modulo 48. Join to for every , and join to . For each , 1, ..., 7, join the six vertices in the cyclic order for . The resulting graph has 432 edges, degree 9, and girth 5. It is isomorphic to the graph in Jørgensen's online adjacency list (Jørgensen).

There are several choices in this construction. On the six labels 0, 1, ..., 5, exactly three undirected Hamiltonian cycles avoid pairs whose difference is modulo 6. These are the allowable cycles for the second set of vertices, since the first set uses the standard 6-cycle graph in each coset. There are 384 seven-element subsets with the stated difference property. Exhaustively using these 384 subsets and each of the three allowable cycles, with the same cyclic order in all eight cosets and with representatives fixed to 0, 1, ..., 7, gives 1152 constructions. Up to graph isomorphism, they yield exactly two graphs. Each occurs 576 times.

More generally, the allowable cycle can be chosen independently in each of the eight cosets. Fixing the displayed then gives constructions and exactly 16 graph isomorphism classes. All 384 allowable subsets are related by transformations with coprime to 48, so allowing other does not add classes in this larger enumeration. Allowing arbitrary coset representatives with a common cyclic order also gives these 16 classes, since translating any allowable 6-cycle runs through all three choices. Isomorphisms here may interchange the two sets of vertices and need not preserve their labels. These counts concern the stated construction, not all 96-vertex -graphs, and do not establish the cage graph order.

Stored examples of specified degree , girth , and order will be implemented in a future version of the Wolfram Language using the forms GraphData["RegularGirth", k, g, n] and GraphData["RegularGirth", k, g, n, i]. The index is needed to distinguish stored examples with the same , , and .