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

v3 · 2026-09-19 · History

Domain-specific #

1935

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Graph Theory → Mathematics

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.

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.

How would you explain it like I'm…

Shortest Loop Count

Picture dots joined by strings. If you walk along the strings and come back to where you started without going back the way you came, you made a loop. The girth is how many strings are in the shortest loop you can find. If there are no loops at all, the girth is called infinity.

Shortest Round Trip

A graph is a set of points (vertices) connected by lines (edges). A cycle is a path that returns to its starting point without reusing an edge. The girth is the number of edges in the shortest cycle in the whole graph. A triangle has girth 3 and a square has girth 4. A graph with no cycles, like a tree, has girth infinity by convention.

Shortest-Cycle Length

The girth of an undirected graph is the length, in edges, of its shortest cycle. If the graph has no cycle, its girth is infinity. Girth tells you how far you can explore from any vertex before the graph stops looking like a branching tree. Large girth means local neighborhoods stay tree-like even if cycles exist farther out. Girth is only one number, though. Two graphs with the same girth can differ in size, degree, and connectivity. And in graphs with loops, repeated edges, or directions, you must say what counts as a cycle before comparing girths.

 

In an undirected graph, the girth is the minimum number of edges in any cycle, and it is set to ∞ for acyclic graphs (forests). It is a global minimum built from local closure: the smallest radius at which a non-backtracking walk can close up. If the girth is g, every ball of radius below roughly g/2 around a vertex is a tree, so large girth means locally tree-like structure. Girth is preserved by graph isomorphism, making it an invariant, but it is a constraint rather than a full description: equal-girth graphs can differ in order, degree sequence, connectivity, expansion, and how cycles are distributed. Conventions matter: in multigraphs a loop gives a cycle of length 1 and parallel edges give length 2, and directed graphs use oriented cycles, so the model must be stated before comparing girths.

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

1. Fix the graph model and admissible-cycle definition.
2. Search for cycles in increasing length or compute shortest return paths around edges.
3. Take the minimum cycle length when a cycle exists.
4. Assign infinity if the graph is acyclic under the stated convention.
5. Translate a girth bound into a radius of local tree-likeness.
6. Combine girth with degree and order for extremal conclusions.
7. 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.

Relationships to Other Abstractions

Current abstraction Girth (Graph Theory) Domain-specific

Parents (1) — outgoing typed relations

• 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) → is a kind of Cycle → presupposes Network

Neighborhood in Abstraction Space

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

Family — Graph Regularity & Width Parameters (6 abstractions)

Nearest neighbors

• Cage (Graph Theory) — 0.85
• Even-hole-free graph — 0.84
• Polygon — 0.82
• Degree diameter problem — 0.81
• Tree (Graph Theory) — 0.81

Computed from structural-signature embeddings · 2026-10-25