Graph girth g(G) = length of shortest cycle. g(tree) = ∞. g(K_n) = 3. g(C_n) = n. g(Petersen) = 5. Fundamental in cage theory: (r,g)-cage is smallest r-regular graph with girth g. Girth constrains graph density and chromatic number.
How to Use
Select graph:
- g: Girth
- ∞: Acyclic
- 3: Has triangles
BFS Algorithm
For each vertex: BFS. If BFS reaches an already-visited vertex (not parent), found a cycle. Track minimum length across all vertices. O(n·(n+m)).
Cage Theory
(r,g)-cage: smallest r-regular graph with girth g. Petersen: (3,5)-cage (10 vertices). Moore bound: n ≥ 1+r+r(r-1)+...+r(r-1)^{(g-3)/2} for odd g. Finding cages is a major open problem!
Step-by-Step Instructions
- 1Select graph.
- 2Run BFS from each vertex.
- 3Detect shortest cycle.
- 4Report girth.
- 5Check: tree → ∞.