3
$\begingroup$

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.

4 Answers 4

3

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

18+18+6=42.

2

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.

  • 0
    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.2012-11-29
2

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".)

  • 0
    I suppose I should also remark that the number 42 includes instances of when not all 3 colours are used.2012-11-29
1

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); 42 

The colourings obtained are as follows:

   abcdef  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