Girth of a graph

Definition

Suppose $G$ is an undirected graph. The girth of $G$ is defined as the minimum possible length of a cycle of length 3 or more (i.e., a subgraph isomorphic to a cycle graph) in $G$.

Related invariants

• Even girth refers to the minimum among the lengths of all cycles of even length.
• Odd girth refers to the minimum among the lengths of all cycles of odd length.

The girth of a graph is the minimum of its even girth and odd girth.

Related graph properties

• Forest and tree: Note that the girth of a graph is $\infty$ if and only if the graph is a forest. For a connected graph, the girth is $\infty$ if and only if the graph is a tree.
• Triangle-free graph is a graph of girth 4 or more