A connected simple graph $G$ with $n$ vertices is a tree if and only if $P_G(x) = x(x − 1)^{n−1}$ .

I need help with understanding the proof of this. I know how the forward direction works and that's pretty straight forward. But I'm quite confused about proving the converse of the statement.

The proof in one of my textbooks makes no sense to me. Let me just show you a quick Lemma you need to know before I show you the proof.

Lemma: Let $$G$$ be a simple graph with $$n$$ vertices and $$m$$ edges. Then the coefficient of $$x^{n-1}$$ in $$P_G(x)$$ is $$-m$$

Now, onto the proof of the converse of the original statement:

"Suppise that $$P_G(x) = x(x − 1)^{n-1}$$. Then by the Binomial Theorem, the expansion of $$(x − 1)^{n−1}$$ starts as $$(x − 1)^{n−1} = x^{n−1} − (n − 1)x^{n−2} + · · ·$$ Therefore $$P_G(x) = x^n − (n − 1)x^{n−1} + · · ·$$

and, by the previous Lemma, G must have n − 1 edges. A connected graph with n vertices. and n − 1 edges must be a tree"

This doesn't make any sense to me because how does a graph of chromatic polynomial $$P_G(x) = x^n − (n − 1)x^{n−1} + · · ·$$ imply that it has $$n-1$$ edges? The Lemma only stated the other direction.

In this case, if a graph has $$n-1$$ edges, then $$P_G(x) = x^n − (n − 1)x^{n−1} + · · ·$$. It did not involve the converse of that statement.

Can someone please explain this to me?

• It would be better to include the definition of $P_G$ in the post. – Saad Apr 25 at 12:07
• @Saad, $P_G$ is the chromatic polynomial, it gives the number of ways to color the vertices of the graph if $x$ colors are available and adjacent vertices must get different colors. – Gerry Myerson Apr 25 at 12:10
• Any thoughts on the two answers posted yesterday, Tim? – Gerry Myerson Apr 27 at 7:48
• I found out the answer eventually. But thanks – Tim Apr 29 at 23:03
• The canonical way to thank someone here, Tim, is to "accept" one of the answers by clicking in the check mark next to it. Or, if you found an answer yourself, you could write it up, post it as an answer, and then accept your own answer. – Gerry Myerson Apr 29 at 23:57

Suppose $$G$$ has $$m$$ edges. Then, by the lemma, the coefficient of $$x^{n-1}$$ in $$P_G$$ equals to $$-m$$.
However, the assumption is that $$P_G$$ is known, and is $$x^n-(n-1)x^{n-1}+\dots$$, so it implies $$m=n-1$$.
If the graph has $$m$$ edges, then that coefficient is $$-m$$. If the graph doesn't have $$m$$ edges, then it has some other number of edges, so that coefficient is some other number, not $$-m$$. So if the coefficient is $$-m$$, then the graph has $$m$$ edges.