GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
940 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked in Graph Theory by Veteran (40.7k points)  
edited by | 940 views

3 Answers

+15 votes
Best answer

Four colour theorem is famous result, it says that any planar graphs can be coloured with only 4 colours !

Ref -> https://en.wikipedia.org/wiki/Four_color_theorem

 

Note for confused people => laugh

 
Here ANY is used in sense of FOR ALL x , so , here ANY means literally any one of graph can be selected !

What are you saying , is something like There exists, but in that case, they will say, That specific graph directly..

Any man alive is gonna die => This means all men are gonna die ! Not specific to anyone !
Hope this clears thing a bit !
answered by Veteran (40.7k points)  
selected by
actually ..I have a question ..null graph is also considerd as planer ..but we can't color null graph with 4 colors?? I think here any is an ambiguous word ..the answer might be 4 but this null graph thing I dont understand..

@abhi150

Hope that you got your answer :) Check answer again !

ok ...got it thanks
i have a question,

planar graphs not in syllabus right ?
I have one doubt the theorem states that no more than 4 colors are required but the ques is asking for minimum, is it not contradictory? I mean if we take two points and join them it can be colored using 2 colors. I am not including single point as disconnected graphs are not considered for coloring. @Akash Kanase @Arjun
even I thought the same ..Null graph is also planer but we can color that by only 1 color..but I think the question here says sufficient to vertex color "any" planer graph ..with just 1 or 2 colors we can't color K4 ..although it would have been much better if they had not used "any" .Any is used as For all x but we should always avoid using Any as it is ambiguous.
Okay so it means min for worst case scenario.. Got it thanks :)
Question is confusing.. At the most 4 colours are used..interpretation of question could vary from person to person :)
But knowing English grammar is also necessary for GATE.
Yeah English and context free too :P
+4 votes
According to four color theorem, Every planar graph can be colored using 4 colors.
answered by Junior (717 points)  
0 votes
@arjun sir : can you verify

as far i know , 4 is neccessary to colour any graph (planar )

but 5 is sufficent one

but since they have asked minimum colour so it should be 4 right ?

Ref : Narisngh deo book
answered by Boss (8.7k points)  
Top Users Jan 2017
  1. Debashish Deka

    8968 Points

  2. sudsho

    5326 Points

  3. Habibkhan

    4798 Points

  4. Bikram

    4532 Points

  5. Vijay Thakur

    4486 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4196 Points

  8. santhoshdevulapally

    3808 Points

  9. Sushant Gokhale

    3596 Points

  10. Kapil

    3486 Points

Monthly Topper: Rs. 500 gift card

19,212 questions
24,104 answers
53,150 comments
20,319 users