The clique polynomial C_G(x) for the graph G is defined as the polynomial C_G(x) = 1 + sum_(k = 1)^(ω(G)) c_k x^k, where ω(G) is the clique number of G, the coefficient of x_k for k>0 is the number of cliques c_k in the graph, and the constant term is 1 (Hoede and Li 1994, Hajiabolhassan and Mehrabadi 1998). Hajiabolhassan and Mehrabadi showed that C_G(x) always has a real root. The coefficient c_1 is the vertex count, c_2 is the edge count, and c_3 is the triangle count in a graph.

clique | clique number