GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
679 views

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

  1. 2
  2. 3
  3. 4
  4. 5
asked in Graph Theory by Veteran (61.6k points)   | 679 views

3 Answers

+9 votes
Best answer

4 colors are required to color the graph in the prescribed way.

answer = option C

answered by Veteran (28.3k points)  
selected by
Practical approach :)
Here we also need to prove that the given graph can't be colored with less than 4 colors.

As it consists cycle with odd vertices it requires at least 3 colors.

But if you try to color them with 3 colors it is not possible to color them with 3 colors.

More ever any planar graph can be colored with 4 colors (Four color theorem).
+2 votes

Ans C 

answered by Veteran (10.4k points)  
–3 votes
The max degree of the vertex is 4 so we need atleast 5 colours to colour the graph
answered by Veteran (13.1k points)  
4 colours are enough here !
It is a planar graph so we need only 4 colour.


Top Users Aug 2017
  1. Bikram

    4902 Points

  2. ABKUNDAN

    4704 Points

  3. akash.dinkar12

    3480 Points

  4. rahul sharma 5

    3158 Points

  5. manu00x

    3012 Points

  6. makhdoom ghaya

    2480 Points

  7. just_bhavana

    2388 Points

  8. stblue

    2138 Points

  9. Tesla!

    2060 Points

  10. joshi_nitish

    1758 Points


25,014 questions
32,139 answers
74,824 comments
30,185 users