Number of proper $x$-coloring, $x \in {1,2,3,4,...}$ of connected graph with $n$ vertices is less than or equal to $x(x-1)^{n-1}$ for $n \geq 1 $.
I think there are two cases that I need to consider
$Case[1]$ If G is connected and has no cycles, then it follows that G is a tree, where chromatic polynomial is just equal to $x(x-1)^{n-1}$
$Case[2]$ If G is connecteded and has some cycles
For second case, I am just not sure how to start proof that chromatic polynomial is less than $x(x-1)^{n-1}$
Also, would it suffice to consider above two cases to prove the claim?
It's not true (if we treat the chromatic polynomial as a polynomial). As a counterexample, take:
the tree $K_{1,2}$ has chromatic polynomial $x(x-1)^2$; and
the complete graph $K_3$ has chromatic polynomial $x(x-1)(x-2)$;
and if we plot these (using Wolfram|Alpha), we see neither is greater than the other for all real $x$, nor for all (or all non-negative) rational $x$, nor for all integers $x$:
However, it is true (from the definition of a chromatic polynomial) if we restrict to non-negative integers. (But this means we don't use the polynomial-ness of the chromatic polynomial; we're just counting colorings.)
Any connected graph $G$ contains spanning tree $T$. The graph $T$ for $x \in \mathbb {Z}^{\geq 0}$ admits $x(x-1)^{n-1}$ distinct $x$-colorings.
Any $x$-coloring of $G$ is an $x$-coloring of $T$.
Thus $P(G;x) \leq P(T;x) = x(x-1)^{n-1}$ for $x \in \mathbb {Z}^{\geq 0}$.