GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
595 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 (59.2k points)   | 595 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 (27.9k points)  
selected by
Practical approach :)
+2 votes

Ans C 

answered by Veteran (10.2k 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 Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users