close
Image TOPICS
Image
Search

Cage Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A (v,g)-cage graph is a v-regular graph of girth g having the minimum possible number of nodes. When v is not explicitly stated, the term "g-cage" generally refers to a (3,g)-cage.

A list of cage graphs can be obtained in the Wolfram Language using GraphData["Cage"]. Related regular graphs of specified degree, girth, and order will be implemented in a future version of the Wolfram Language as GraphData[{"RegularGirth", {d, g, n}}].

There are a number of special cases (Wong 1982). The (2,g)-cage is the cycle graph C_g, the (v,2)-cage is the multigraph of v edges on two vertices, the (v,3)-cage is the complete graph K_(v+1), and the (v,4)-cage is the bipartite graph K_(v,v).

Let n(v,g) be the number of vertices in the (v,g)-cage graph. Then the following table summarizes exactly known values of n(v,g) for small values of g and v from 3 to 7. The value n(3,11)=112 was found by McKay et al. (1998).

gn(3,g)n(4,g)n(5,g)n(6,g)n(7,g)
SloaneA000066
345678
468101214
51019304050
61426426290
72467
83080170312
958
1070
11112
1212672827307812

Computing the number of n(v,g) vertices in a (v,g)-cage is very difficult for g>=5 and v>=3 (Wong 1982). A lower bound n_l(v,g)<=n(v,g) is given by

n_l(v,g)={(v(v-1)^((g-1)/2)-2)/(v-2) for g odd; (2(v-1)^(g/2)-2)/(v-2) for g even
(1)

(Tutte 1967, p. 70; Bollobás 1978, p. 105; Wong 1982). For v=3, this gives the sequence of lower limits n_l(3,g) for g=1, 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) obtained the general upper bounds

n_u(3,g)={4/3+(29)/(12)2^(g-2) for g odd; 2/3+(29)/(12)2^(g-2) for g even
(2)
n_u(v,g)={2(v-1)^(g-2) for g odd; 4(v-1)^(g-3) for g even,
(3)

with v>=4 (Wong 1982).

For some pairs (v,g), the order of a (v,g)-cage is not exactly known. The following table gives known bounds for the corresponding cage orders.

(v,g)bounds for n(v,g)references
(3,13)[202,272]Biggs (1998), McKay et al. (1998)
(3,14)[262,384]Exoo (2002), de la Cruz and Pizaña (2026)
(3,15)[388,620]Biggs and Hoare (1983), de la Cruz and Pizaña (2026)
(4,9)[165,270]Exoo et al. (2025), de la Cruz and Pizaña (2026)
(4,10)[245,320]Exoo and Jajcay (2011), Exoo et al. (2025)
(5,7)[110,152]Exoo and Jajcay (2011), de la Cruz and Pizaña (2026)
(6,7)[189,294]Exoo and Jajcay (2011)
(9,5)[86,96]Jørgensen (2005), Exoo and Jajcay (2011)
(10,5)[103,124]Exoo and Jajcay (2011), House of Graphs
(11,5)[124,154]Exoo and Jajcay (2011), House of Graphs
(11,6)[224,240]Wong (1982), Exoo and Jajcay (2011)
(12,5)[147,203]Exoo and Jajcay (2011)
(13,5)[174,226]Exoo and Jajcay (2011), House of Graphs
(14,5)[199,280]Exoo and Jajcay (2011), House of Graphs

The reference column cites primary sources when they are available, and otherwise uses the survey of Exoo and Jajcay (2011) or House of Graphs for tabulated bounds. See also the online tabulations of Brouwer and Royle.

The following table summarizes known cage graphs.

(v,g)countsnamed cages (or references)
(3,3)1complete graph K_4
(3,4)1complete bipartite graph K_(3,3)
(3,5)1Petersen graph
(3,6)1Heawood graph
(3,7)1McGee graph
(3,8)1Tutte 8-cage
(3,9)18Biggs and Hoare (1980), Brinkmann et al. (1995)
(3,10)3Balaban 10-cage, Harries graph, Harries-Wong graph
(3,11)1Balaban 11-cage; Balaban (1973), Myrvold and McKay
(3,12)1Tutte 12-cage; Polster et al. (1998, p. 179)
(4,3)1complete graph K_5
(4,4)1complete bipartite graph K_(4,4)
(4,5)1Robertson graph
(4,6)1Wong (1982)
(4,7)>=1Exoo (2007)
(4,8)>=1Royle
(4,12)>=1generalized dodecagon GD(1,3)
(5,3)1complete graph K_6
(5,4)1complete bipartite graph K_(5,5)
(5,5)4Wong graph, Foster cage, Meringer graph, Robertson-Wegner graph
(5,6)>=1Royle
(5,8)>=1Royle
(5,12)>=1Royle
(6,3)1complete graph K_7
(6,4)1complete bipartite graph K_(6,6)
(6,8)>=1Royle
(6,12)>=1Royle
(7,3)1complete graph K_8
(7,4)1complete bipartite graph K_(7,7)
(7,5)1Hoffman-Singleton graph
(8,8)>=1Royle
(9,8)>=1Royle
(10,8)>=1Royle
(12,8)>=1Royle
(14,6)>=1Royle
(14,8)>=1Royle
CageGraphs3

Cubic (v=3) 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 (3,g)-cage for all g>=3, and the (3,g)-cages are unique for g=3 to 8. A selection of known (3,g)-cages are illustrated above (Read and Wilson 1998, pp. 271-272). The unique (3,8)-cage is the Tutte 8-cage (Read and Wilson 1998, p. 271). The first (3,9)-cage was found by Biggs and Hoare (1980), and Brinkmann et al. (1995) completed an exhaustive search yielding all 18 (3,9)-cages (Royle). One of them is illustrated by Holton and Sheehan (1993, p. 197). The three (3,10)-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 (3,11)-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 (3,g) cages for g=3, 4, ... are given by 1, 1, 1, 1, 1, 1, 18, 3, 1, 1, ... (OEIS A052453; Gould 1988, Royle).

CageGraphs4

The known (4,g)-cages are illustrated above (Wong 1982). In March 2007, Exoo et al. conclusively identified one (4,7)-cage.

CageGraphs5

Some (5,g)-cages are shown above (Wong 1982). Meringer (1999) showed that there are four (5,5)-cages, despite the fact that Wong (1982) had indicated that only three such cages existed.

The Hoffman-Singleton graph is a (7,5)-cage.

Cage graphs for which the lower bound of equation (1) gives the actual number of vertices are known as Moore graphs.

See also

Balaban 10-Cage, Cayley Graph, Cubic Graph, Excess, Foster Cage, Harries Graph, Harries-Wong Graph, Heawood Graph, Hoffman-Singleton Graph, McGee Graph, Meringer Graph, Moore Graph, Petersen Graph, Regular Graph, Robertson Graph, Robertson-Wegner Graph, Tutte 8-Cage, Wong Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships among the Cages." Rev. Roumaine Math. Pures Appl. 18, 1033-1043, 1973.Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Biggs, N. L. "Constructions for Cubic Graphs with Large Girth." Elec. J. Combin. 5, No. 1, A1, 1-25, 1998. https://doi.org/10.37236/1386.Biggs, N. L. and Hoare, M. J. "A Trivalent Graph with 58 Vertices and Girth 9." Disc. Math. 30, 299-301, 1980.Biggs, N. L. and Hoare, M. J. "The Sextet Construction for Cubic Graphs." Combinatorica 3, 153-165, 1983.Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.Brinkmann, G.; McKay, B. D.; and Saager, C. "The Smallest Cubic Graphs of Girth Nine." Combin., Probability, and Computing 5, 1-13, 1995.Brouwer, A. E. "Cages." https://aeb.win.tue.nl/graphs/cages/cages.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Cages." §6.9 in Distance Regular Graphs. New York: Springer-Verlag, 1989.de la Cruz, C. M. and Pizaña, M. A. "On Cages and Choosing with Symmetries." Elec. J. Combin. 33, No. 1, P1.54, 1-19, 2026. https://doi.org/10.37236/14471.Erdős, P. and Sachs, H. "Reguläre graphen gegebener Taillenweite mit minimaler Knotenzahl." Wiss. Z. Uni. Halle (Math. Nat.) 12, 251-257, 1963.Exoo, G. "A Small Trivalent Graph of Girth 14." Elec. J. Combin. 9, No. 1, N3, 1-2, 2002. https://doi.org/10.37236/1664.Exoo, G.; Goedgebeur, J.; Jooken, J.; Stubbe, L.; and van den Eede, T. "New Small Regular Graphs of Given Girth: The Cage Problem and Beyond." Nov. 10, 2025. https://arxiv.org/abs/2511.07247.Exoo, G. and Jajcay, R. "Dynamic Cage Survey." Electronic J. Combinatorics, Dynamic Survey DS16, 2011. https://www.maths.tcd.ie/EMIS/journals/EJC/Surveys/ds16.pdf.Exoo, G.; McKay, B.; and Myrvold, W. "A (4,7)-Cage." https://isu.indstate.edu/~gexoo/CAGES/g4.7.67.Exoo, G.; McKay, B. D.; Myrvold, W.; and Nadon, J. "Computational Determination of (3,11) and (4,7) Cages." J. Discrete Algorithms 9, 166-169, 2011. https://doi.org/10.1016/j.jda.2010.11.001.Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Holton, D. A. and Sheehan, J. Ch. 6 in The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.House of Graphs. "Cages." https://houseofgraphs.org/meta-directory/cages.Jørgensen, L. K. "Girth 5 Graphs from Relative Difference Sets." Disc. Math. 293, 177-184, 2005.McKay, B. D.; Myrvold, W.; and Nadon, J. "Fast Backtracking Principles Applied to Find New Cages." In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, January 1998. New York: ACM, pp. 188-191, 1998.Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.O'Keefe, M. and Wong, P. K. "A Smallest Graph of Girth 10 and Valency 3." J. Combin. Th. B 29, 91-105, 1980.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: Papers in Applied Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Polster, B. A Geometrical Picture Book. New York: Springer-Verlag, p. 179, 1998.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 271-274, 1998.Update a linkRoyle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/Royle, G. "Cages of Higher Valency." https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, I." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 9-25, 1967a.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, II." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 27-43, 1967b.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 191 and 221, 1990.Sloane, N. J. A. Sequences A000066/M1013, A027383, A037233, and A052453 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc. 43, 459-474, 1947.Tutte, W. T. Connectivity in Graphs. Toronto, Canada: Toronto University Press, pp. 70-83, 1967.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Referenced on Wolfram|Alpha

Cage Graph

Cite this as:

Weisstein, Eric W. "Cage Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CageGraph.html

Subject classifications