$A$ graph $G$ arises from $G_{1}$ and $G_{2}$ by pasting them along $S$ if $G$ has induced subgraphs $G_{1}$, $G_{2}$ with $G=G_{1}\cup G_{2}$ and $S$ is such that $S=G_{1}\cap G_{2}.$ A is graph is called chordal if it can be constructed recursively by pasting along complete subgraphs, starting from complete subgraphs. For a graph $G(V,E)$ define its Hilbert polynomial $H_{G}(x)$ to be $H_{G}(x)=1+Vx+Ex^2+c(K_{3})x^3+c(K_{4})x^4+\ldots+c(K_{w(G)})x^{w(G)},$ where $c(K_{i})$ is the number of $i$-cliques in $G$ and $w(G)$ is the clique number of $G$. Prove that $H_{G}(-1)=0$ if and only if $G$ is chordal or a tree.
Problem
Source:
Tags: algebra, polynomial, geometry, geometric transformation, reflection, combinatorics unsolved, combinatorics