# The Cage Problem

From Combinatorics Wiki

## The Cage Problem

This problem, also known as the degree/girth problem, is closely related to the degree/diameter problem.

**Degree/girth problem**: Given natural numbers *d≥2* and *g≥3*, find the smallest possible number
*n(d,g)* of vertices in a regular graph of degree *d* and girth *g*.

A regular graph of degree *d*, girth *g* and minimum possible order is called a *(d,g)*-cage. Tutte was the first to study *(d,g)*-cage. However, researchers became really interested in this class of graphs when
Erdos and Sachs proved that a *(d,g)*-cage
exists for all *d≥2* and *g≥3*, implying that the function *n(d,g)* is defined for any *d≥2* and *g≥3*. At present only a few
*(d,g)*-cages are known. The state-of-the-art in the study of cages can
be found in the recently published survey by Exoo and Jajcay.

It turns out that lower bounds for *(d,g)*-cage depends on the parity of *g*; that is why the degree/girth problem is often divided into the degree/girth problem for odd girth and the degree/girth problem for even girth.

**Degree/girth problem for odd girth**: Given natural numbers *d≥2* and odd *g≥3*, find the smallest possible number
*n(d,g)* of vertices in a regular graph of degree *d* and girth *g*.

**Degree/girth problem for odd girth**: Given natural numbers *d≥2* and even *g≥3*, find the smallest possible number
*n(d,g)* of vertices in a regular graph of degree *d* and girth *g*.

The Moore bound represents not only an upper bound on the number *N(d,k)* of vertices of a graph of maximum degree *d* and
diameter *k*, but it is also a lower bound on the number *n ^{o}(d,g)* of vertices of a
regular graph of degree

*d*and girth

*2k+1*. A

*(d,g)*-cage of order

*M(d,k)*is therefore a Moore graph if

*g=2k+1*.

The Moore bipartite bound represents not only an upper bound on the number of vertices of a bipartite graph of maximum degree *d* and
diameter *k*, but it is also a lower bound on the number *n ^{e}(d,g)* of vertices of a
regular graph of degree

*d*and girth

*g=2k*.

Then a preamble about tables....

Now a link to a table for trivalent graphs.

## References

- G. Exoo and R. Jajcay (2008), "Dynamic cage survey", The Electronic Journal of Combinatorics, Dynamic survey DS16 PDF version.