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.

  • 1
    $\begingroup$ It would be better to include the definition of $P_G$ in the post. $\endgroup$ – Saad Apr 25 at 12:07
  • $\begingroup$ @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. $\endgroup$ – Gerry Myerson Apr 25 at 12:10
  • $\begingroup$ Any thoughts on the two answers posted yesterday, Tim? $\endgroup$ – Gerry Myerson Apr 27 at 7:48
  • $\begingroup$ I found out the answer eventually. But thanks $\endgroup$ – Tim Apr 29 at 23:03
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ Thanks for that $\endgroup$ – Tim Apr 29 at 23:03

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.

  • $\begingroup$ Thanks very much. $\endgroup$ – Tim Apr 29 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.