A 
-cage graph is a 
-regular graph of girth 
having the minimum possible number of
nodes. When 
is not explicitly stated, the term "
-cage" generally refers to a 
-cage.
A list of cage graphs can be obtained in the Wolfram Language using GraphData["Cage"].
There are a number of special cases (Wong 1982). The 
-cage is the cycle graph 
, the 
-cage is the multigraph
of 
edges on two vertices, the 
-cage is the complete graph 
, and the 
-cage is the bipartite graph 
.
Let 
be the number of vertices in the
-cage graph. Then the following table
summarizes exactly known values of 
for small values of 
and 
from 3 to 7. The value 
was found by McKay et al. (1998).
 |  |  |  |  |  |
| Sloane | A000066 | ||||
| 3 | 4 | 5 | 6 | 7 | 8 |
| 4 | 6 | 8 | 10 | 12 | 14 |
| 5 | 10 | 19 | 30 | 40 | 50 |
| 6 | 14 | 26 | 42 | 62 | 90 |
| 7 | 24 | 67 | 152 | 294 | |
| 8 | 30 | 80 | 170 | 312 | |
| 9 | 58 | 275 | |||
| 10 | 70 | 384 | |||
| 11 | 112 | ||||
| 12 | 126 | 728 | 2730 | 7812 |
Computing the number of 
vertices in a 
-cage
is very difficult for 
and 
(Wong 1982). A lower bound 
is given by
 |
(1)
|
(Tutte 1967, p. 70; Bollobás 1978, p. 105; Wong 1982). For 
, this gives the sequence of lower
limits 
for 
, 2, ... of 4, 6, 10, 14, 22, 30, 46,
62, 94, 126, 190, 254, ... (OEIS A027383),
which agrees with the actual values as far as they are known.
Sauer (1967ab) has obtained the best upper bounds known
 |  |  |
(2)
|
 |  |  |
(3)
|
with 
(Wong 1982).
The following table summarizes known cage graphs.
 | counts | named cages (or references) |
 | 1 | complete
graph  |
 | 1 | complete
bipartite graph  |
 | 1 | Petersen graph |
 | 1 | Heawood graph |
 | 1 | McGee graph |
 | 1 | Tutte 8-cage |
 | 18 | Biggs and Hoare (1980), Brinkmann et al. (1995) |
 | 3 | Balaban 10-cage, Harries graph, Harries-Wong graph |
 | 1 | Balaban 11-cage; Balaban (1973), Myrvold and McKay |
 | 1 | Tutte 12-cage; Polster et al. (1998, p. 179) |
 | 1 | complete
graph  |
 | 1 | complete
bipartite graph  |
 | 1 | Robertson graph |
 | 1 | Wong (1982) |
 |  | Exoo (2007) |
 |  | Royle |
 |  | generalized
dodecagon  |
 | 1 | complete graph  |
 | 1 | complete bipartite graph  |
 | 4 | Wong graph, Foster cage, Meringer graph, Robertson-Wegner graph |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 | 1 | complete
graph  |
 | 1 | complete
bipartite graph  |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 | 1 | complete
graph  |
 | 1 | complete
bipartite graph  |
 | 1 | Hoffman-Singleton graph |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 |  | Royle |
 |  | Royle |
Cubic (
)
cages were first discussed by Tutte (1947), but the intensive study of cage graphs
did not begin until publication of an article by Erdős and Sachs (1963). There
exists a 
-cage
for all 
,
and the 
-cages
are unique for 
to 8. A selection of known 
-cages
are illustrated above (Read and Wilson 1998, pp. 271-272). The unique 
-cage is the Tutte 8-cage
(Read and Wilson 1998, p. 271). The first 
-cage was found by Biggs and Hoare (1980), and Brinkmann
et al. (1995) completed an exhaustive search yielding all 18 
-cages (Royle). One of them is illustrated by Holton and
Sheehan (1993, p. 197). The three 
-cages were found by O'Keefe and Wong (1980; Read and
Wilson 1998, p. 272). Computations by McKay and W. Myrvold have demonstrated
that a 
-cage
must have 112 vertices (McKay et al. 1998, Royle), and the single known example
was found by Balaban (1973) and is sometimes known as the Balaban
10-cage. Myrvold and McKay subsequently proved that the minimal graph on 112
vertices is unique (B. D. McKay, pers. comm., May 20, 2003). The number
of nonisomorphic 
cages for 
,
4, ... are given by 1, 1, 1, 1, 1, 1, 18, 3, 1, 1, ... (OEIS A052453;
Gould 1988, Royle).
The known 
-cages
are illustrated above (Wong 1982). In March 2007, Exoo et al. conclusively
identified one 
-cage.
Some 
-cages are shown above (Wong 1982).
Meringer (1999) showed that there are four 
-cages, despite the fact that Wong (1982) had indicated
that only three such cages existed.
The Hoffman-Singleton graph is a 
-cage.
Cage graphs for which the lower bound of equation (1) gives the actual number of vertices are known as Moore graphs.
