# A graph $G$ is connected iff the coefficient of $x$ in $P(G,x)$ is nonzero?

I was talking to my brother today, and we came up with a little conjecture. Is it true that a graph $G$ of order $n$ is connected if and only if the coefficient of $x$ in the chromatic polynomial $P(G,x)$ is nonzero? This was inspired by results like the coefficient of $x^n$ is always $1$, the constant term is always $0$, the coefficient $x^{n-1}=-|E|$, etc.

We were able to prove one direction. Suppose $G$ is disconnected. Then $G$ is the union of disconnected components, say $H$ and $K$ for simplicity's sake, and so $P(G,x)=P(H,x)P(K,x)$. But since the constant term of a chromatic polynomial is always $0$, then the least term of $P(H,x)P(K,x)$ is at least $x^2$ since the least monomial term of each is $x$, and so the coefficient of $x$ is $0$.

However, we couldn't quite complete the other direction. Our idea was to take $G$ to be a connected graph. Then $G$ has a spanning tree, with chromatic polynomial $x(x-1)^{n-1}$, which has $(-1)^{n-1}$ as its coefficient for $x$. I figured you could then recover the original graph by adding edges back, and using the fact that $P(G,x)=P(G\setminus e,x)-P(G/e,x)$ to somehow induct, but we couldn't complete the argument. So is the reverse direction true? If so, how to prove it? And if not, is there a counterexample? Thank you.

-
I think 9.47 here gives you what you need –  Juan S Apr 23 '11 at 0:49
@Qwirk, thanks, I'll try to get a hold of that and take a deeper look. –  yunone Apr 23 '11 at 1:00
@Qwirk, I was looking around in that book, and in 9.39 they use the notation $f_{(n)}$, saying the coefficient of $x^{n-1}$ in $f_{(n)}$ is $-(1/2)(n)(n-1)$. Do you happen to know what this notation $f_{(n)}$ means? –  yunone Apr 23 '11 at 23:37
sorry, not sure! –  Juan S Apr 26 '11 at 23:44

## 1 Answer

Wikipedia says your conjecture is correct. If $G$ has $k$ connected components, then the coefficient of $t^k$ in the chromatic polynomial is non-zero, and all the coefficient of $t^l$ for $l<k$ is zero. This pretty much sums up your result.

-
Thanks Thomas, I guess this answers my question in more generality. –  yunone Apr 23 '11 at 18:18
It's actually not really that much more general. Basically, the number of colorings of a disconnected graph with $k$ colors is triviallly the product of the number of colorings of each component, so this "general" rule actually follows from the specific rule for the connected graph (your conjecture.) –  Thomas Andrews Apr 23 '11 at 18:23