Cage (Graph Theory)¶

An r-regular graph of girth g having the minimum possible number of vertices among all graphs with that degree and girth.

Version: v4 · 2026-09-19 · History
Domain-specific #: 1427
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics
Aliases: (r,g)-cage, Regular cage graph

Core Idea¶

For integers \(r\ge2\) and \(g\ge3\), an ((r,g))-graph is an ®-regular graph whose girth—the length of its shortest cycle—is exactly (g). An ((r,g))-cage is such a graph with the smallest possible order (number of vertices). Multiple nonisomorphic cages may attain the same minimum.^[1]

The recognition invariant is fixed degree + fixed girth + global minimum order + graph considered up to isomorphism. A small regular graph is only a cage after minimality is established against every competing graph with the same parameters.

How would you explain it like I'm…

The Fewest-Dots Loop Puzzle

Draw dots and connect them with strings so every dot has the same number of strings. Then look for the smallest loop you can walk around, and make it a certain size. A cage is a drawing like that which uses the fewest dots anyone could possibly use.

Smallest Graph with Long Loops

In graph theory, a graph is a bunch of dots (vertices) connected by lines (edges). Pick two numbers: r, how many lines touch each dot, and g, how long the shortest loop in the graph must be (its girth). A cage is a graph where every dot has exactly r lines, the shortest loop has exactly length g, and there is no other such graph with fewer dots. Sometimes more than one different graph ties for the smallest size, and they are all cages. Just finding a small graph that fits isn't enough; you have to show that nothing smaller exists.

Minimum-Order Regular Graph of Given Girth

For whole numbers r ≥ 2 and g ≥ 3, an (r, g)-graph is a graph in which every vertex has degree r (it is r-regular) and whose girth, the length of the shortest cycle, is exactly g. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices. There can be several cages for the same pair (r, g) that are not isomorphic, meaning they are genuinely different graphs rather than relabelings of one another. The key requirement is global minimality: you need to prove that no (r, g)-graph with fewer vertices exists. A small regular graph with the right girth is only a candidate until that minimality is established, which distinguishes cages from arbitrary regular graphs with a given girth.

For integers r ≥ 2 and g ≥ 3, an (r, g)-graph is an r-regular graph whose girth, the length of its shortest cycle, is exactly g. An (r, g)-cage is an (r, g)-graph of minimum order, meaning it has the fewest vertices among all (r, g)-graphs. Cages are considered up to isomorphism, and several nonisomorphic cages may attain the same minimum order. The recognition invariant therefore combines four ingredients: fixed degree, fixed girth, global minimum order, and identification up to isomorphism. Establishing that a given graph is a cage requires a minimality argument against every competing graph with the same parameters, not merely exhibiting a small regular graph with the correct girth. This minimality condition is what separates the cage problem, finding the smallest regular graphs with no short cycles, from the easier task of constructing some graph with the required degree and girth.

Structural Signature¶

Finite simple graph convention stated.
Degree parameter ® and regularity at every vertex.
Girth parameter (g) and no shorter cycle.
Candidate order (n).
Lower bound, commonly the Moore bound, for the parameter pair.
Construction attaining a claimed upper bound.
Minimality proof closing the gap.
Isomorphism classification where uniqueness is claimed.
Possible multiple extremizers.
Named incidence, algebraic, or computational construction.
Existence distinguished from identification of the exact minimum.
Exceptional low-degree cases bounded separately.
Asymptotic order–girth tradeoff for families.

What It Is Not¶

It is not any graph with high girth, nor the smallest graph found by a search. “Cage” includes a theorem-level minimality claim. It is not necessarily a Moore graph: Moore graphs attain the general Moore lower bound, whereas a cage can be larger when that bound is unattainable.^[2]

It is not the cage graph used in chemistry or geometry by lexical analogy. Nor does uniqueness follow from minimum order; several nonisomorphic graphs can share cage parameters.

Scope of Application¶

Cages are studied in extremal graph theory, finite geometry, incidence structures, algebraic constructions, exhaustive generation, and sparse network design. They probe how locally tree-like an ®-regular graph can remain before cycles are forced.^[3]

Canonical examples include the Petersen graph as the ((3,5))-cage, the Heawood graph as the ((3,6))-cage, and the Tutte–Coxeter graph as the ((3,8))-cage.

Clarity¶

“Girth (g)” means the shortest cycle has exactly length (g), not merely at least (g), unless a source explicitly uses a different extremal convention. Degree is exact and uniform.

Lower bounds and constructions play different roles: a construction proves an upper bound on cage order; a counting argument proves a lower bound. Only equality, or exclusion of every intermediate order, proves the cage.

Manages Complexity¶

The ((r,g)) parameters compress a large graph-search space into one extremal question. Breadth-first expansion from a vertex or edge yields Moore-type bounds, while symmetry and canonical labeling reduce computational duplication.

The remaining difficulty is global: local degree/girth checks are easy, but minimum order and nonisomorphism demand proof or exhaustive certified search.

Abstract Reasoning¶

Fix graph conventions, ®, and (g).
Derive the appropriate lower bound by tree expansion.
Construct or locate an ®-regular graph with girth (g).
Verify regularity and compute the shortest cycle.
Compare its order with the bound.
If a gap remains, exclude smaller orders analytically or computationally.
Canonically classify all minimizers before claiming uniqueness.
Separate exact cage results from best-known upper bounds.

Knowledge Transfer¶

The portable structure is constrained extremal minimization: preserve two local/global invariants while minimizing resource size. The proposed immediate parent is Optimization.

Examples¶

Petersen graph. It is cubic, has girth five, and has ten vertices; the Moore bound gives ten, proving it is a ((3,5))-cage.

Multiple minimizers. A parameter pair may admit several nonisomorphic graphs of the same minimum order; the abstraction belongs to each graph, not just one canonical drawing.

Non-example. A 3-regular graph of girth five on twelve vertices is an ((3,5))-graph but not a cage because the Petersen graph has ten.

Structural Tensions¶

Local tree-likeness versus finite closure.
Lower bounds versus attainable constructions.
Minimum order versus uniqueness.
Exact results versus best-known candidates.
Symmetry-rich examples versus asymmetric extremizers.
Analytical proof versus exhaustive computation.

Structural–Framed Character¶

Constraint, minimization, lower bound, extremizer, and equivalence are structural. Regular graphs, girth, cycles, Moore bounds, and graph isomorphism are domain frame.

Structural Core vs. Domain Accent¶

The portable core is a smallest object satisfying fixed constraints. Degree, girth, vertices, cycles, incidence constructions, and isomorphism are constitutive domain accent.

This entry is a kind of Optimization.

Optimization is the broader abstraction this entry instantiates. Lower Bound, Constraint Satisfaction, Symmetry, Equivalence Relation, and Search are related. Turán Graph solves a different extremal problem; Tree (Graph Theory) has no cycles and therefore no finite girth.

Relationships to Other Abstractions¶

Current abstraction Cage (Graph Theory) Domain-specific

Parents (1) — outgoing typed relations

Cage (Graph Theory) is a kind of Optimization Prime

Optimization is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

Cage (Graph Theory) → is a kind of Optimization

Neighborhood in Abstraction Space¶

Cage (Graph Theory) sits in a sparse region of the domain-specific corpus (68^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Extremal Graph Theory & Bounds (7 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With¶

Any regular high-girth graph.
A Moore graph.
A best-known but unproved minimum.
A unique graph for each ((r,g)).
Tree or SPQR-tree structures.
A geometric or physical cage.

References¶

[1] Pak-Ken Wong, “Cages—A Survey”, Journal of Graph Theory 6 (1982): 1–22. registry ↩ Show verification details

[2] Norman Biggs, Algebraic Graph Theory, 2^nd ed., Cambridge University Press, 1993. registry ↩

[3] Geoffrey Exoo and Robert Jajcay, “Dynamic Cage Survey,” Electronic Journal of Combinatorics, Dynamic Survey DS16, 2008 and updates.not authoritative registry ↩ Show verification details

[4] W. T. Tutte, “A Family of Cubical Graphs,” Proceedings of the Cambridge Philosophical Society 43 (1947): 459–474. registry ↩