Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

for a homework graph theory, I'm asked to determine the chromatic polynomial of the following graph

this is my thread in another post:

For the Descomposition Theorem of Chromatic Polynomials. if G=(V,E), is a connected graph and e belong E

P (G, λ) = P (Ge, λ) -P(Ge', λ)

When calculating chromatic Polynomials, i shall place brackets about a graph to indicate its chromatic polynomial. removes an edge any of the original graph to calculate the chromatic polynomial by the method of decomposition.

 P (G, λ) = P (Ge, λ)-P (Ge ', λ) = λ (λ-1) ^ 3 - [λ (λ-1) (λ^2 - 3λ + 3)]

But the response from the answer key and the teacher is:

P (G, λ) = λ (λ-1)(λ-2)(λ^2-2λ-2)

I have operated on the polynomial but I can not reach the solution that I ask .. what am I doing wrong?

share|cite|improve this question
up vote 2 down vote accepted

Your graph is a 5-cycle. I wouldn't use that theorem, I'd just do it directly.

1st vertex: $\lambda$ options.

2nd vertex: $\lambda-1$ options.

3rd vertex: two cases. If it's the same color as 1st vertex, then $\lambda-1$ options for 4th vertex, $\lambda-2$ options for 5th vertex. So this case contributes $\lambda(\lambda-1)^2(\lambda-2)$. Second case, if it differs from the 1st vertex ($\lambda-2$ options), then two subcases: if 4th vertex is same color as 1st, then $\lambda-1$ options for 5th, making $\lambda(\lambda-1)(\lambda-2)(\lambda-1)$. If 4th differs from 1st ($\lambda-2$ options), then $\lambda-2$ options for 5th, making $\lambda(\lambda-1)(\lambda-2)^3$.

Now add 'em all up.

share|cite|improve this answer
I did not know that you can not apply the theorem for graphs 5-cycles. I do not understand why you can not. – franvergara66 Apr 20 '11 at 1:56
You can; all I'm saying is that I wouldn't, because I'd find it easier to just reason my way through this problem. – Gerry Myerson Apr 20 '11 at 2:16

I think what you need in your answer is $\lambda (\lambda- 1)^4$ for the polynomial of Ge. The 5-cycle with one edge removed is a path of five vertices. $\lambda$ choices for the first, and $(\lambda - 1)$ choices for the other 4.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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