Consider the following hexagon with the shown vertices connected:

Wheel graph

We now add additional connections:

i) e is connected to b

ii) c is connected to d

ii) a is connected to f

How many ways can we color each point either red, white, or blue such that connected points have different colors?

I am HORRIBLE bad with these problems. I was thinking casework but I cannot seem to ensure I have all the cases.


It's helpful to remark that each vertex of $a,b,c$ is connected to each vertex of $d,e,f$.

This graph is called $K_{3,3}$, the complete bipartite graph of size $(3,3)$ and many things are known about it, but there's also the direct approach:

If $a,b,c$ take three different colors, there is nothing left for $d$.

If they take two different colors, all the other vertices have to take the remaining color. There are 18 possiblities for this (3 choices for the vertex with a lonely color, 3 choices for its color and 2 choices for the color of the other two, the rest is fixed, then).

If they take a single color, the other three vertices can either take the two other colors which gives again 18 by symmetry, or also have a single color, this gives 6 possibilites (3 choices for the first color, 2 choices for the second color).



I don't see an easy way besides case work, but you can use symmetry to your advantage. You can just decide that a is red and multiply by 3 at the end because there is nothing yet to distinguish the colors. Then d must be a different color, so call it white and multiply by 2 at the end (again, white and blue are equivalent until now), making a factor 6. Then b can only be red or blue because of d. If it is blue, you know all the rest-one case. If it is red, you still have a bit of work to do.

  • $\begingroup$ right, that's what i assumed, that it would unfortunately resort to casework. But I was wondering if someone could display all the cases and the final answer. It would be much appreciated. I just get bogged down by all the cases. $\endgroup$ – Ankan Nov 29 '12 at 21:24

You could compute the chromatic polynomial. In this case the polynomial is $$x^6-9x^5+36x^4-75x^3+78x^2-31x$$ which when evaluated at $x=3$ is $42$. So there are $42$ ways of colouring the graph with adjacent vertices receiving different colours.

It seems likely, if you have been asked this question, you're intended to use deletion/contraction or addition/identification until you reach graphs with known chromatic polynomials (although, this doesn't sound particularly easy to do by hand).

(If you're happy with a computational solution: I computed this using a program for computing the Tutte polynomial (here), but you could probably find simpler software to compute it via a Google search for "chromatic polynomial software".)

  • $\begingroup$ That solution of chromatic polynomials seems like... magic :). Can you please explain how you arrived at the chromatic polynomial and why you plugged in 3? It seems very interesting but I have never heard about it and the Wikipedia article seems too dense for me to comprehend $\endgroup$ – Ankan Nov 29 '12 at 22:03
  • $\begingroup$ Well... it turns out the number of ways of (properly) colouring a graph with up to $x$ colours, is a polynomial in $x$. Computing the chromatic polynomial is, however, the difficult part, and is usually done by recursively applying deletion/contraction (it's only really "magic" since I left out this legwork from my answer). $\endgroup$ – Douglas S. Stones Nov 29 '12 at 22:35
  • $\begingroup$ I suppose I should also remark that the number 42 includes instances of when not all 3 colours are used. $\endgroup$ – Douglas S. Stones Nov 29 '12 at 22:36

As another way, this can be computed directly (i.e. brute force) in GAP as follows:

gap> edges:=[[1,2],[2,3],[3,4],[4,5],[5,6],[6,1],[1,4],[2,5],[3,6]];;
gap> S:=Filtered(Tuples([1,2,3],6),C->ForAll(edges,e->C[e[1]]<>C[e[2]]));;
gap> Size(S);

The colourings obtained are as follows:


1  rwrwrw
2  rwrwrb
3  rwrwbw
4  rwrbrw
5  rwrbrb
6  rwbwrw
7  rwbwbw
8  rbrwrw
9  rbrwrb
10 rbrbrw
11 rbrbrb
12 rbrbwb
13 rbwbrb
14 rbwbwb
15 wrwrwr
16 wrwrwb
17 wrwrbr
18 wrwbwr
19 wrwbwb
20 wrbrwr
21 wrbrbr
22 wbrbrb
23 wbrbwb
24 wbwrwr
25 wbwrwb
26 wbwbrb
27 wbwbwr
28 wbwbwb
29 brwrwr
30 brwrbr
31 brbrwr
32 brbrbr
33 brbrbw
34 brbwbr
35 brbwbw
36 bwrwrw
37 bwrwbw
38 bwbrbr
39 bwbrbw
40 bwbwrw
41 bwbwbr
42 bwbwbw

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.