Skip to main content
`Ctrl`+`K`

# girth

girth(G)

  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:
    G NetworkX 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