Girth

Remarks

In a simple graph each cycle has length at least $3$, so the girth is at least $3$. Example: the cycle graph $C_n$ with $n \ge 3$ has girth $n$, since its only cycle has length $n$. The complete graph $K_n$ with $n \ge 3$ has girth $3$, and the complete bipartite graph $K_{m,n}$ with $m, n \ge 2$ has girth $4$, since a bipartite graph has no odd cycle. The Petersen graph has girth $5$. Non-example: in the path graph $u - v - w$, the closed walk $u, v, u$ has length $2$ but is not a cycle, because it uses the edge $uv$ twice. The path graph has no cycle, so its girth is $\infty$. Every tree has girth $\infty$. The girth is sometimes written $g(G)$.