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.
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.
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.
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.
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.
Relationships to Other Abstractions¶
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
- Cage (Graph Theory) → Optimization
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
- Degree diameter problem — 0.87
- Girth (Graph Theory) — 0.85
- Homogeneous Graph — 0.83
- Cubic Graph — 0.83
- Reconstruction conjecture — 0.82
Computed from structural-signature embeddings · 2026-09-08