edited by
4,039 views
37 votes
37 votes

A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph.

How many vertex colouring with three colours does this graph have?

  1. $3^9$
  2. $6^3$
  3. $3 \times 2^8$
  4. $27$
  5. $24$
edited by

4 Answers

Best answer
43 votes
43 votes

Start with the Inner one which can be filled in $\Rightarrow 3\times 2\times 1 = 6$ ways.

Then, middle one can be filled in $\Rightarrow 2\times 1\times 1 = 2$ ways.

Then, similarly outermost can be filled in $\Rightarrow 2\times 1\times 1 = 2$ ways.


Hence, Total number of ways to fill this figure $\Rightarrow 6\times 2\times 2 = 24$ ways.

Correct Answer: $E$

edited by
7 votes
7 votes
The answer is E (24).

Start with the innermost triangle.

u1, u2, u3 must be coloured separately as they are connected to each other. Therefore, if u1 is coloured red, u2 and u3 must be coloured with (green and blue) or (blue and green) respectively. Hence, allocating a single colour to u1 brings two choices and u1 can be coloured with three differnet colours, hence total ways in innermost triangle can be coloured is 3 X 2 = 6 ways.

Now, after colouring the inner triangle come to the middle one. For instance, If we had coloured the inner triangle, u1-> red, u2-> blue,  u3-> green, the v1 vertex can be coloured only blue or green, since it is connected to u1 vertex, similarly v2 can be coloured with red or green since v2 is connected to u2, and similarly v3 being directly connected to u3 can coloured either with red or blue.

Summarizing the choices below ->

v1 -> blue or green

v2 -> red or green

v3 -> red or blue

and, v1, v2,v3 must be coloured with different colour as they are directly connected to each other.

Lets suppose we colour v1 blue, then v3 must be coloured red, and then v2 must be coloured green. Another option can be v1 ->green, v2->red, v3->blue.

So, for each innermost triangle colouring there exists two separate colourings for the middle triangle.

And, in a similar way for each middle triangle colouring there exists two colourings of the outermost triangle.

Total colouring = product of colouring of innermost, middle, outermost triangle colouring.

= 6 X 2 X 2 = 24.
5 votes
5 votes

simple and easy 

Start with the innermost triangle , Innermost triangle can be coloured in 3! ways . means vertex u1 has 3 choices, u2 has remaining 2 choices , u3 has only 1 choice.

so  innermost triangle can be coloured in 6 ways.

now if we come to middle triangle here we can use the concept of dearrangement. bcoz anyhow we try to dearrange the colours that means try to avoid the same colour not match with same colour by using dearrangement formula

Dn =$\sum_{r=0}^{n} (-1)^{r} n!/r!$

Dn=2

so 2 ways to colour the middle triangle.

now for outermost triangle the same concept of dearrangement is used.

so we can colour outermost triangle with 2 ways .

now total no of ways to colour the whole graph G is = 3! * 2 * 2

=24 ways

edited by
0 votes
0 votes
The inner 3 vertices can take up the three colors in $3!=6$ ways

The next 3 vertices can take up the colors in such a way that the vertices will not be colored with the same color as the corresponding adjacent inner vertex.

we here can have the number of derangement of 3 colors in the 2nd layer vertices because we just need to derange the colors on the inner vertices such that the original colors will not be there in there original position so no. of derangement = $\left \lfloor \frac{3!}{e} \right \rfloor \quad=2$

 

similarly we can work out for outer set of vertices = 2

so, answer is $6 \times2 \times 2 = 24$
Answer:

Related questions