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

3 Answers

+6 votes
Best answer

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

answer = option C

answered by Veteran (27.5k 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 (13k points)  
4 colours are enough here !
It is a planar graph so we need only 4 colour.
Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,989 answers
59,623 comments
22,046 users