Skip to content

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
v3 · 2026-09-06 · History
Domain-specific #
1427
Origin domain
mathematics
Subdomain
graph theory
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.

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

  1. Fix graph conventions, ®, and (g).
  2. Derive the appropriate lower bound by tree expansion.
  3. Construct or locate an ®-regular graph with girth (g).
  4. Verify regularity and compute the shortest cycle.
  5. Compare its order with the bound.
  6. If a gap remains, exclude smaller orders analytically or computationally.
  7. Canonically classify all minimizers before claiming uniqueness.
  8. 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.

Optimization is the proposed immediate parent. 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.

The prospective queue contains one strict edge to prime:optimization. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for Cage (Graph Theory)Parents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Cage (Graph Theory)DOMAINPrime abstraction: Optimization — is a kind ofOptimizationPRIME

Current abstraction Cage (Graph Theory) Domain-specific

Parents (1) — more general patterns this builds on

  • Cage (Graph Theory) is a kind of Optimization Prime

    Optimization is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

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

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

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 ↩

[2] Norman Biggs, Algebraic Graph Theory, 2nd 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. registry ↩

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