Let the vertices be $x_1, ..., x_n$. Let $X$ be the set $\{a:\text{the subgraph of } G \text{ induced by the vertex set }a \cong H \}$

Consider the number of assignments of $1 ... t$ to $x_1, ..., x_n$ such that the constraints "Not all of $x_k$ $(k\in a)$ have the same value" are satisfied for all $a\in X$. These assignments correspond to the colorings that avoid having a monochromatic $H$.

Now I will prove the number is polynomial in $t$ for any family of sets $X$ on $1 ... n$. The proof is based on induction on the number of vertices and then the size of $X$.

The statement is of course true for an empty set of vertices. Say the statement is true for all numbers of vertices less than $n$.

• $X= \emptyset$. Trivial.

• Suppose the number is polynomial for $|X|=m-1$. Then, for $X'=X \cup \{x\}$, (the number of solutions violating at least one constraint in $X'$)=(the number of solutions violating at least one constraint in $X$)+(the number of solutions violating the constraint on $x$)-(the number of solutions violating at least one constraint in $X$ and the constraint on $x$) by the inclusion-exclusion principle.

If $x$ is empty or having only one element, all solutions would violate the constraint on $x$ so the statement is true. So we will assume $x$ has at least $2$ elements.

The first term on the RHS is polynomial in $k$ by induction on size of $X$.

The second term is polynomial by simple counting.

The third term is polynomial by replacing all the $x_a$ $(a \in x)$ by a single variable (because all the $x_a$ are equal) in order to reduce the number of varibles, and it's polynomial by induction on $n$.

So the number of solutions violating at least one statement in $X'$ is polynomial in $k$, and thus, the number of solutions fulfilling all statements in $X'$ is polynomial in $k$.

By the use of mathematical induction on the size of $X$, we can prove the statement for every $n$ assuming its truth for every smaller $n$.

By the use of mathematical induction on $n$, the statement is true for any $n$.

Let the vertices be $x_1, ..., x_n$. Let $X$ be the set $\{a:\text{the subgraph of } G \text{ induced by the vertex set }a \cong H \}$

Consider the number of assignments of $1 ... t$ to $x_1, ..., x_n$ such that the constraints "Not all of $x_k$ $(k\in a)$ have the same value" are satisfied for all $a\in X$. These assignments correspond to the colorings that avoid having a monochromatic $H$.

Now I will prove the number is polynomial in $t$ for any family of sets $X$ on $1 ... n$. The proof is based on induction on the number of vertices and then the size of $X$.

The statement is of course true for an empty set of vertices. Say the statement is true for all numbers of vertices less than $n$.

• $X= \emptyset$. Trivial.

• Suppose the number is polynomial for $|X|=m-1$. Then, for $X'=X \cup \{x\}$, (the number of solutions violating at least one constraint in $X'$)=(the number of solutions violating at least one constraint in $X$)+(the number of solutions violating the constraint on $x$)-(the number of solutions violating at least one constraint in $X$ and the constraint on $x$) by the inclusion-exclusion principle.

If $x$ is empty or having only one element, all solutions would violate the constraint on $x$ so the statement is true. So we will assume $x$ has at least $2$ elements.

The first term on the RHS is polynomial in $k$ by induction on size of $X$.

The second term is polynomial by simple counting.

The third term is polynomial by replacing all the $x_a$ $(a \in x)$ by a single variable (because all the $x_a$ are equal) in order to reduce the number of varibles, and it's polynomial by induction on $n$.

So the number of solutions violating at least one constraint in $X'$ is polynomial in $k$, and thus, the number of solutions satisfying all constraints in $X'$ is polynomial in $k$.

By the use of mathematical induction on the size of $X$, we can prove the statement for every $n$ assuming its truth for every smaller $n$.

By the use of mathematical induction on $n$, the statement is true for any $n$.