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

I'm supposed to determine chromatic polynomial of a $8$-vertex graph, which is the result of sticking

There are two complete $5$-vertex graphs, each with one edge removed, in the first graph we remove the edge $uv$ and in the second graph we remove $u'v'$. Then we stick the graphs together by putting $u=u'$ and $v=v'$ . I hope the description is quite clear, because I don't know how to insert the image of this graph.

It seems pointless to try using the recurrence formula for chromatic polynomial of a graph (by trying to get complete graphs by contracting together two unconnected vertices and drawing an additional edge linking them).

Could you help me with that?

share|cite|improve this question
If we take two copies of $K_5$ and merge two vertices in one copy with two vertices in the other, the resulting graph has only eight vertices. – Chris Godsil Jan 29 '13 at 19:29
Oh, right, it is an 8-vertice graph. – Hagrid Jan 29 '13 at 20:59
up vote 2 down vote accepted

It's easy to see this from first principles: remember that $P(x)$ is the number of colourings of the graph using $x$ colours.

If you fix the colours of the two vertices in the middle (which used to be $u$ and $v$), then the remaining graph splits into two separate complete graphs which are very simple to count colourings in.

(At this point you should ask yourself: if there are $3$ ways to colour each copy, how many different ways are there to colour both together? Hint: it's not $6$.)

The exact number of colourings of each complete graph (as a function of $x$) depends on whether you colour $u$ and $v$ the same colour or distinct colours, so consider these two cases separately, and remember to account for how many ways there are to choose the two initial colours.

share|cite|improve this answer
Well, if we consider a graph with 5 vertices where $u$ and $v$ are not connected then for such a graph if $u$ and $v$ have different colours we get x(x-1)(x-2)(x-3)(x-4) possible colourings and if $u$ and $v$ have the same colours we get x(x-1)(x-2)(x-3) possible colourings. Now, the answer in my textbook is $\frac{(x(x-1)(x-2)(x-3)(x-4))^2}{x(x-1)} + \frac{(x(x-1)(x-2)(x-3))^2}{x}$. Could you tell me what to do next? Or did I just understand you incorrectly? – Hagrid Jan 29 '13 at 21:23
@Hagrid You're on the right track but you need to take into account that your graph contains two such graphs of 5 vertices. There are $x(x-1)$ ways to choose $u$ and $v$ with different colours, and $x$ ways to choose them with the same colour. How many choices for the remaining 6 vertices? It helps if you have given some thought about where formulas like $x(x-1)(x-2)(x-3)$ come from. – Erick Wong Jan 29 '13 at 21:41
From the picture that @Robert Israel presented below we can see that if $u, \ v$ have the same colour, then we choose colour of the base and then of the vertices of three triangles in x(x-1)(x-2)(x-3) ways and if their colours are different we do it in x(x-1)(x-2)(x-3)(x-4) ways. Is that correct? – Hagrid Jan 29 '13 at 22:09
@Hagrid Let's make this more concrete by picking, say $x=6$. There are $6\cdot 5 = 30$ ways to colour $u$ and $v$ differently. Now there are $4$ colours remaining, since we cannot reuse $u$ and $v$'s colours: how many ways can you colour all six remaining vertices? (Certainly there is more freedom in colouring two triangles than just one of them.) – Erick Wong Jan 29 '13 at 22:41
Having coloured the two middle vertices (1 and 2), we can the colour the "3" in 4 ways, "4" in 3 ways and "5" in 2 ways. Since We can repeat it for "3'", "4'", "5'" because they are not directly linked to "3", "4", "5". – Hagrid Jan 29 '13 at 23:10

I assume this is your graph. Shown is a 4-colouring. It's easy to see there are $4$-cliques, so the chromatic number is $4$.

enter image description here

EDIT: I suggest you look at two separate cases, where $1$ and $2$ have the same colour and where they have different colours. Note that given the colours of vertices $1$ and $2$, vertices $3$, $4$ and $5$ can have any three different colours that are not those of $1$ and $2$, and similarly for $3'$, $4'$ and $5'$.

share|cite|improve this answer
But the question asks for the chromatic polynomial, not the chromatic number. – Chris Godsil Jan 29 '13 at 21:33
Yes, but see the last paragraph. – Robert Israel Jan 29 '13 at 21:47

So, here's the graph:

The OP's graph

and another method for finding the chromatic polynomial.

We can use the addition/identification law on the vertices $x$ and $y$ to compute the chromatic polynomial. The law states that if $x$ and $y$ are not adjacent, then the $$P(G,\lambda)=P(G+xy,\lambda)+P(G/xy,\lambda).$$

In this case, the chromatic polynomial of the above graph is the sum of the chromatic polynomials of the graphs:

Addition of edge $xy$


Identification of $x$ and $y$

These graphs are clique separable copies of complete graphs. Thus, they have the chromatic polynomials $$\frac{P(K_5;\lambda)^2}{P(K_2;\lambda)}$$ and $$\frac{P(K_4;\lambda)^2}{P(K_1;\lambda)},$$ respectively.

The chromatic polynomial of the complete graph $K_n$ is $$P(K_n;\lambda)=\lambda(\lambda-1)\cdots(\lambda-n+1).$$

Hence the chromatic polynomial of the original graph is: $$\frac{\big(\lambda(\lambda-1)(\lambda-2)(\lambda-3)(\lambda-4)\big)^2}{\lambda(\lambda-1)}+\frac{\big(\lambda(\lambda-1)(\lambda-2)(\lambda-3)\big)^2}{\lambda}$$ which simplifies to $$\lambda(\lambda-1)(\lambda-2)^2(\lambda-3)^2(\lambda-7\lambda+15).$$

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.