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

Question

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?

Thank you in advance.

Answer 1

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$.

Answer 2

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.