GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
152 views

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$
asked in Graph Theory by Veteran (77.2k points)  
edited by | 152 views

2 Answers

+14 votes
Best answer

Start with the Inner one which can be filled in => $3 * 2 * 1 = 6$ ways

Then, middle one can be filled in => $2 * 1 * 1 = 2$ ways

Then, similarly outermost can be filled in => $2 * 1 * 1 = 2$ ways


Hence, Total number of ways to fill this figure => $6 * 2 * 2 = 24$ ways

answered by Veteran (47.2k points)  
selected by
0 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.
answered by Junior (995 points)  


Top Users May 2017
  1. akash.dinkar12

    3140 Points

  2. pawan kumarln

    1606 Points

  3. sh!va

    1580 Points

  4. Arjun

    1316 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1020 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    970 Points

  9. LeenSharma

    796 Points

  10. srestha

    658 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    232 Points

  2. jjayantamahata

    106 Points

  3. joshi_nitish

    106 Points

  4. Ahwan

    96 Points

  5. Aditya GN

    63 Points


22,717 questions
29,045 answers
65,029 comments
27,454 users