What is the smallest possible graph that maintains a specific degree and cycle length?

What is the smallest possible graph that maintains a specific degree and cycle length?
Image: Intellect (generated)

In short: In graph theory, a cage is a regular graph designed to be as compact as possible while maintaining a required degree and girth. These structures are not just theoretical curiosities; they represent the absolute limit of efficiency in connecting nodes without creating cycles shorter than a specified threshold.

A cage is formally defined as an (r, g)-graph, where every vertex connects to exactly r neighbors and the shortest cycle in the graph—the girth—is exactly g. The primary challenge in this field is finding the smallest number of vertices required to satisfy these two constraints simultaneously. Because 1-regular graphs lack cycles and 2-regular graphs have a girth equal to their vertex count, researchers focus on graphs where r is at least 3.

The size of these graphs is constrained by the Moore bound, which provides a theoretical minimum for the number of vertices. If a graph hits this lower bound exactly, it is called a Moore graph and is guaranteed to be a cage. For instance, the famous Petersen graph is a (3, 5)-cage with 10 vertices, while the Hoffman–Singleton graph serves as the (7, 5)-cage with 50 vertices. However, cages are not always unique; for a (3, 10) configuration, there are three distinct, non-isomorphic graphs, all containing 70 vertices.

As the required girth g increases, the number of vertices needed grows exponentially. This relationship is captured by logarithmic bounds. While the Moore bound provides an upper limit on how large the girth can be relative to the number of vertices, other constructions, such as Ramanujan graphs developed by Lubotzky, Phillips, and Sarnak in 1988, provide lower bounds on girth. These mathematical structures help mathematicians understand the trade-offs between connectivity and cycle length in complex networks, proving that even in abstract graph theory, there are rigid physical limits to how densely we can pack information.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-cage-graph-theory.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…