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.

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.

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) — 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