Skip to main content
`Ctrl`+`K`

# is_chordal

is_chordal(G)

  Checks whether G is a chordal graph.

  A graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle).

  Parameters:
    G graph

      A NetworkX graph.

  Returns:
    chordal bool

      True if G is a chordal graph and False otherwise.

  Raises:
    NetworkXNotImplemented

      The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

  Notes

  The routine tries to go through every node following maximum cardinality search. It returns False when it finds that the separator for any node is not a clique. Based on the algorithms in [1].

  Self loops are ignored.

  References

  [1]

  R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.

  Examples

      >>> e = [
      ...     (1, 2),
      ...     (1, 3),
      ...     (2, 3),
      ...     (2, 4),
      ...     (3, 4),
      ...     (3, 5),
      ...     (3, 6),
      ...     (4, 5),
      ...     (4, 6),
      ...     (5, 6),
      ... ]
      >>> G = nx.Graph(e)
      >>> nx.is_chordal(G)
      True