Skip to main content
`Ctrl`+`K`

# Graph Polynomials

Provides algorithms supporting the computation of graph polynomials.

Graph polynomials are polynomial-valued graph invariants that encode a wide variety of structural information. Examples include the Tutte polynomial, chromatic polynomial, characteristic polynomial, and matching polynomial. An extensive treatment is provided in [1].

For a simple example, the `charpoly` method can be used to compute the characteristic polynomial from the adjacency matrix of a graph. Consider the complete graph `K_4`:

    >>> import sympy
    >>> x = sympy.Symbol("x")
    >>> G = nx.complete_graph(4)
    >>> A = nx.to_numpy_array(G, dtype=int)
    >>> M = sympy.SparseMatrix(A)
    >>> M.charpoly(x).as_expr()
    x**4 - 6*x**2 - 8*x - 3

[1]

Y. Shi, M. Dehmer, X. Li, I. Gutman, “Graph Polynomials”

`tutte_polynomial`(G) | Returns the Tutte polynomial of `G`
`chromatic_polynomial`(G) | Returns the chromatic polynomial of `G`