girth#

Returns the girth of the graph.

The girth of a graph is the length of its shortest cycle, or infinity if the graph is acyclic. The algorithm follows the description given on the Wikipedia page [1], and runs in time O(mn) on a graph with m edges and n nodes.

Parameters:

GNetworkX Graph

Returns:

int or math.inf

References

[1]

Wikipedia: Girth

Examples

All examples below (except P_5) can easily be checked using Wikipedia, which has a page for each of these famous graphs.

>>> nx.girth(nx.chvatal_graph())
4
>>> nx.girth(nx.tutte_graph())
4
>>> nx.girth(nx.petersen_graph())
5
>>> nx.girth(nx.heawood_graph())
6
>>> nx.girth(nx.pappus_graph())
6
>>> nx.girth(nx.path_graph(5))
inf