GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
548 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 (58.4k points)   | 548 views

3 Answers

+7 votes
Best answer

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

answer = option C

answered by Veteran (27.7k points)  
selected by
Practical approach :)
+2 votes

Ans C 

answered by Veteran (10.3k 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 Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,063 answers
63,297 comments
24,169 users