# Thread: help with annoying question that needs a bit of logic

1. ## help with annoying question that needs a bit of logic

Im taking a SMC test soon and was looking over a past paper, but had a little trouble with q13:
UKMT Senior Mathematical Challenge 2006 (scroll to q13)

I ended up with 30 after some time, but am also suspicious that the answer could be 36.

Either way, I would still like some kind of logical approach to tackle this problem as I rarely practice this kind of question.

Thanks.

2. I think that you are correct. The answer is 30.
However, that depends on the fact that the two colourings that I have shown are counted as different. I am not at all sure that there are different.

That figure is known in graph theory as an unlabeled graph.
The second figure that I give is a labeled graph and in that case the two colourings are clearly different. This graph is known as a bipartite graph. We can be partitioned into two set of vertices: {A,C} & {B,D,E}. There is no edge between any two vertices is the same cell. There are 3 ways to colour A & C the same colour. Hence there are $2^3$ ways to colour B, D, & E some other colour. That gives us 24 ways. But there are 6 ways to colour A & C with different colours leaving only one way to colour B, D, & E: a total of 30 for the labeled graph.

I would argue that the question is not clear on the point.

POST SCRIPT.
I have just proved that there are only 24 ways to colour an unlabeled graph.
That is not one of the answers. So we must conclude that the question is about a labeled graph.

3. well, i dont know if my logic is correct but i think it this way..
if you label it a,...,e and take any arbitrary circle, then you can choose any color for it, hence, there are three possibilities, while depending on this situation, other circles are left with two colors to choose from. therefore, the answer is 48.

4. Originally Posted by Plato
.....
This graph is known as a bipartite graph. We can be partitioned into two set of vertices: {A,C} & {B,D,E}. There is no edge between any two vertices is the same cell. There are 3 ways to colour A & C the same colour. Hence there are $2^3$ ways to colour B, D, & E some other colour. That gives us 24 ways. But there are 6 ways to colour A & C with different colours leaving only one way to colour B, D, & E: a total of 30 for the labeled graph.
....
i think, you have mistaken that A and C have 3 ways, note that if A have 3 ways, B, E have two ways, and that C are left with 2 ways (supposing B, E have same color, which is possible since they are not connected) since its color depends on B, D and/or E (you can also suppose that B, D and E have same color). This is also true for the other circles.