1.5k views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
edited | 1.5k views

For PLANAR  GRAPHS There are........

vertex colouring for vertices

map colouring for regions

and

edge colouring for edges

IN THE QUESTION planar graph requires ( MINIMUM ) vertex colouring .

1)

DRAW A GRAPH WITH 2 VERTICES AND ONE EDGE

( ie.,  v=2 , e = 1 , f =1 )  IS  A PLANAR GRAPH .

AND IT SATISFIES EULER FORMULA  .( v - e + f  = 2 )

The  minimum Colours  it require = 2.

2)

Take a rectangle with out diagonals .

Is a planar graph  AND   by vertex colouring it requires  2  colors .

THE MINIMUM NO OF COLOURS SUFFICIENT  TO  vertex colour   ANY  planar graph  = 2

In above question ANY plannar graph is said. Means you need to find the maximum no. of vertex-color among all the planner graph. And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

Take a Triangle you will required 3 color.

PLSE

GIVE AN EXAMLE GRAPH
In any planar graph ,

consider a tree

every tree is a planar grapgh and it is triangle free graph

a tree with n vertices requires 2 colours.

for example

a tree with 100 vertices having 99 edges , it requires minimum two colours.
You need to consider every planner graph. Triangle is also a planner graph but you can't color it with 2 color. You need 3. which implies 2 color is not sufficient to color any planner graph.
It is little bit language problem. Just read the comment given below the selected answer.

yes

ANY plannar graph  Means we need to find the maximum no. of vertex-color among all the planner graphs And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

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 =>

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 !
selected
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..

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
According to four color theorem, Every planar graph can be colored using 4 colors.
@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

For PLANAR  GRAPHS There are........

vertex colouring for vertices

map colouring for regions

and

edge colouring for edges

IN THE QUESTION planar graph requires ( MINIMUM ) vertex colouring .

1)

DRAW A GRAPH WITH 2 VERTICES AND ONE EDGE

( ie.,  v=2 , e = 1 , f =1 )  IS  A PLANAR GRAPH .

AND IT SATISFIES EULER FORMULA  .( v - e + f  = 2 )

The  minimum Colours  it require = 2.

2)

Take a rectangle with out diagonals .

Is a planar graph  AND   by vertex colouring it requires  2  colors .

THE MINIMUM NO OF COLOURS SUFFICIENT  TO  This  planar graph  = 2

ALSO

In any planar graph ,

consider a tree

every tree is a planar grapgh and it is triangle free graph

a tree with n vertices requires 2 colours.

for example

a tree with 100 vertices having 99 edges , it requires minimum 2 (two ) colours.

3)

consider a triangle  with 3 vertices & 3 edges

it requires  minimum 3 colours

4)

consider a wheel graph of 4 vertices

it requires  minimum 4 colours

5)

cosider  a complete graph of 4 vertices  (k4)

it requires  minimum 4 colours

6)cosider  a complete graph of 5 vertices  (k5)

it requires  minimum 5 colours with respect to vertex colour , but  k5 is NON PLANAR

IN THE GIVEN QUESTION

ANY plannar graph  Means we need to find the maximum no. of vertex-color among all the planner graphs And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

SO

edited by