Girth (Graph Theory)¶

Assign an undirected graph the length of its shortest cycle, using infinity for an acyclic graph, to quantify how far local neighborhoods remain tree-like.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1935
Origin domain: mathematics
Subdomain: graph theory
Aliases: Graph girth

Core Idea¶

The girth of an undirected graph is the number of edges in its shortest cycle. If the graph has no cycle, its girth is conventionally infinity. Girth is a global minimum extracted from local closure: it records the earliest path length at which a walk can return to its start without merely retracing an edge. Large girth means neighborhoods remain tree-like to a larger radius even when the graph eventually contains cycles.^[1]

The value is an invariant of graph isomorphism and a constraint rather than a complete description. Graphs with the same girth can differ in size, degree, connectivity, expansion, and cycle distribution. In multigraphs or directed graphs, loops, parallel edges, and orientation change what counts as a cycle, so the graph model and convention must be declared before comparing values.

Structural Signature¶

Declared graph class. Simplicity, direction, loops, and parallel edges determine admissible cycles.
Cycle set. Closed simple paths are enumerated conceptually or algorithmically.
Length rule. Cycle size is counted in edges under the chosen convention.
Minimum operator. The shortest admissible cycle determines the invariant.
Acyclic extension. Forests receive infinite girth.
Local tree-likeness radius. Balls smaller than roughly half the girth contain no cycle.
Extremal constraint. Degree, order, and girth jointly bound possible graph structure.

What It Is Not¶

Not circumference. Circumference is the length of a longest cycle.
Not graph diameter. Diameter measures greatest shortest-path distance between vertices.
Not the number of cycles. A graph can have many cycles while sharing the same minimum length.
Not a cage. A cage minimizes graph order subject to degree and girth constraints.
Not automatically defined the same way for directed graphs or multigraphs. Cycle conventions matter.

Scope of Application¶

Girth is literal wherever a graph model and cycle convention are fixed. It is a mathematical invariant with applications that interpret short loops as dependence, redundancy, or local non-tree structure.

Extremal graph theory. Bounding graph size from degree and forbidden short cycles.
Cage problems. Seeking smallest regular graphs of specified girth.
Coding theory. Designing sparse bipartite graphs without short iterative-dependence loops.
Network algorithms. Characterizing how long local tree approximations remain valid.
Geometric and group theory. Studying Cayley graphs and complexes through short relations.
Random graphs. Comparing local weak limits and short-cycle distributions.

Clarity¶

State graph type, whether length counts edges, and the acyclic convention. When using girth as a proxy for algorithmic independence or local tree-likeness, specify the radius and additional assumptions; a single shortest cycle does not describe how common cycles are elsewhere. Distinguish 'girth at least g' from 'girth exactly g.'

Manages Complexity¶

One integer summarizes the earliest topological obstruction to tree structure. It enables strong exclusion arguments and extremal bounds without listing all cycles. The minimum is also brittle: adding one short cycle can collapse girth even if the rest of a massive network remains tree-like, so applications often need cycle counts or local girth alongside the global value.

Abstract Reasoning¶

Fix the graph model and admissible-cycle definition.
Search for cycles in increasing length or compute shortest return paths around edges.
Take the minimum cycle length when a cycle exists.
Assign infinity if the graph is acyclic under the stated convention.
Translate a girth bound into a radius of local tree-likeness.
Combine girth with degree and order for extremal conclusions.
Add local or distributional diagnostics when the global minimum is unrepresentative.

Knowledge Transfer¶

The general structure is a Cycle invariant refined by minimization: the first closed path sets the scale at which tree-like behavior fails. That transfers literally across graph-based domains. The word girth in geometry or ordinary language is unrelated unless the object is a graph with a declared cycle-length rule.

The graph model must be fixed before the number is meaningful. In a finite simple undirected graph, a cycle uses distinct vertices except for the repeated start, so its length is at least three. A loop would create length one and parallel edges can create length two in a multigraph. Directed girth requires a consistently oriented directed cycle. Some authors study the girth of incidence structures or matroids through related circuit notions, but those are transfers with their own carriers. A reported value without graph type can therefore differ by convention rather than mathematics.

The shortest-cycle definition supports several equivalent diagnostics. Breadth-first search from a vertex builds a tree of shortest paths; an edge connecting two already reached branches can close a cycle whose length is read from their depths and common ancestry. Repeating from all relevant roots finds the minimum in an unweighted graph. A proof of large girth instead shows that every neighborhood out to a stated radius is acyclic. The local tree-like radius is roughly half the girth, with parity determining the exact boundary at which an extra edge can close a cycle.

Small examples calibrate the invariant. A tree and forest have infinite girth under the standard convention. A triangle has girth three even if it also contains longer cycles. A square grid with no diagonals has local four-cycles, while adding one diagonal creates a triangle and lowers girth. A complete graph on at least three vertices has girth three. These cases show that girth is a minimum: adding one short cycle can change the value even when almost all of the graph remains sparse or tree-like.

The invariant does not measure how many cycles exist. One graph can have a single shortest cycle and another exponentially many, yet both have the same girth. Nor does high girth guarantee low degree, good expansion, large diameter, or robustness. Regular high-girth graphs are studied because degree and local tree-likeness together impose useful constraints, but each property must be verified separately. Conversely, a graph with low girth can still have excellent connectivity or expansion.

Extremal questions expose the structure. A regular graph with prescribed degree and girth must contain enough vertices to support the expanding tree neighborhoods before closure occurs. A cage seeks the smallest graph meeting degree and girth constraints. The counting argument depends on whether the girth is odd or even and grows outward from a vertex or an edge. The result is a lower bound and recognition framework, not a guarantee that a graph attaining it exists for every parameter pair.

Applications should preserve the distinction between local and global. In coding or network contexts, short cycles may create undesirable local feedback or correlation, so designers seek larger girth. The application-specific consequence is not part of the definition and may depend on cycle multiplicity, message algorithm, or edge weights. A graph advertised as locally tree-like should state the radius and graph sequence; one finite girth value alone does not imply an asymptotic property.

Weighted graphs add another boundary. Ordinary girth counts edges, not total weight. The minimum-weight cycle can differ from the minimum-length cycle, and zero or negative weights change algorithmic behavior. If the question concerns physical distance or cost, the weighted invariant must be named rather than substituting an unweighted girth computed from the same adjacency.

The strict parent Cycle is literal because girth is obtained by selecting a shortest member from the graph's cycle family, with infinity assigned when that family is empty. Minimum, Distance, and Locality help analyze the value, but none supplies the closed-path object being minimized. The domain-specific residual includes graph conventions, edge count, local tree radius, extremal bounds, and cycle-detection logic. This makes Girth autonomous while keeping it narrower than the parent.

Examples¶

Canonical¶

A square has girth 4 because its only simple cycle uses four edges. A tree has no cycle and therefore infinite girth. The Petersen graph has girth 5: it contains 5-cycles but no triangle or 4-cycle.^[1] These cases show finite minimum, acyclic extension, and the role of forbidden shorter cycles.

Mapped back: graph class → admissible cycles → edge lengths → minimum → girth or infinity.

Applied / In Practice¶

In a Tanner graph for an iterative decoder, a 4-cycle makes two constraint nodes exchange information through overlapping variables after very few iterations. Requiring larger girth delays this reuse and supports a tree-like independence approximation. Designers still inspect the number and arrangement of longer cycles because equal girth does not guarantee equal decoding behavior.

Mapped back: sparse graph → short-cycle search → girth constraint → local tree approximation → residual cycle-distribution check.

Structural Tensions¶

Global invariant vs. local defect. One exceptional short cycle controls the whole value. Diagnostic: Is global girth representative of most vertices?
Tree-likeness vs. eventual closure. Large girth postpones loops but does not remove them. Diagnostic: At what radius does the application reuse information?
Degree vs. girth vs. order. Improving one constraint forces cost in another. Diagnostic: Which extremal trade-off governs the design?
Simple definition vs. graph-model variation. Loops and direction change admissible cycles. Diagnostic: What graph category is being compared?
Minimum length vs. cycle abundance. Equal minima can hide different distributions. Diagnostic: Is a cycle count or local profile also needed?

Structural–Framed Character¶

Shortest-cycle minimization is highly structural and almost unframed, but graph, edge, cycle, and length conventions are constitutive mathematical vocabulary. Its portability is across graph substrates, not all domains without representation as a graph.

Structural Core vs. Domain Accent¶

The skeleton is closed-return structures → length → minimum obstruction scale. The accent is graph-theoretic cycle and edge machinery. Removing it yields a generic minimum or recurrence notion, while Cycle already carries the cross-domain closed-path prime.

Cycle is the strict parent because finite girth is defined by the shortest cycle and infinite girth by the absence of cycles. Cage (Graph Theory) is a constrained extremal neighbor, not a parent.

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

Relationships to Other Abstractions¶

Current abstraction Girth (Graph Theory) Domain-specific

Parents (1) — more general patterns this builds on

Girth (Graph Theory) is a kind of Cycle Prime

Cycle is the strict parent because finite girth is defined by the shortest cycle and infinite girth by the absence of cycles.

Hierarchy path (1) — routes to 1 parentless root

Girth (Graph Theory) → Cycle → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Girth (Graph Theory) sits in a sparse region of the domain-specific corpus (82^nd 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¶

Circumference (graph theory). Longest rather than shortest cycle length.
Diameter. Maximum distance between vertices under shortest paths.
Cage. A smallest regular graph satisfying degree and girth conditions.
Cycle rank. Counts independent cycles algebraically rather than their minimum length.
Local girth. Shortest cycle through a specified vertex or edge, which can differ across a graph.

References¶

[1] Reinhard Diestel, Graph Theory, 5^th ed. (Springer, 2017). registry ↩a ↩b