GATE CSE 2016 | Set 2 | Question: 03

Question

The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

Comments

Answer is =4

We need minimum 4 colors which is sufficient to vertex color any planar graph

---

@Anyone what, if its ask for cromatic index???

---

https://www.geeksforgeeks.org/four-color-theorem-and-kuratowskis-theorem-in-discrete-mathematics/

Answer 1

Four color theorem is a famous result and it says that any planar graphs can be colored with only $4$ colors.

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

Note for confused people  😄

Here ANY is used in sense of FOR ALL $x$. i.e., ANY means literally any one of graph can be selected !
Any man alive is gonna die $\Rightarrow$ All men are gonna die and not any specific one.

Hope this clears thing a bit !

Comments

Theorem 5.10.6

(Five Color Theorem) Every planar graph can be colored with 5 colors.

REF : https://www.whitman.edu/mathematics/cgt_online/book/section05.10.html

Why here it is showing 5 colors??

---

see here it is saying a planar graph is  4-colorable , 5- colorable as well as 6- colorable.

-> http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/theorems.html

and I think it is obvious that if a graph is 4 colorable then we can color it easily with more than 4 colors as well (as many vertices it have)!

---

so any means within that context only we need to see we cant go out of bound

Answer 2

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  (k₄)

it requires  minimum 4 colours 

6)cosider  a complete graph of 5 vertices  (k₅)

it requires  minimum 5 colours with respect to vertex colour , but  k₅ 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

                              answer is 4

Answer 3

According to four color theorem, Every planar graph can be colored using 4 colors.

Answer 4

If we talk about minimum no. of colors that is sufficient to vertex-color in any planar graph which means a planar graph with any no. of vertices. However, in some cases, 3 colors are suffcient to vertex-color in a planar graph like triangle whereas in some cases 4 colors are suffcient to vertex-color in a planar graph . But is has been proved that 4 colors are sufficient to vertex-color every planar graph. It is called as the four color theorem. So, the answer will be 4.

Answer 5

Note that we have asked about the sufficient condition ie the worst case condition hence for determining minimum colours sufficient for any planar graph we would find the first non-planar graph.

According to Kuratowski's first non-planar graph is a complete graph having 5 vertices ie K5 and all the prior graphs like K4,K3,..  are all planar .

Hence we know that max colouring number for a graph appears to the equal to number of vertices in graph ie in worst case we can have max colouring number equal to number of vertices and not more than that which is only possible in complete graph.

So max colouring number in any planar graph will be 4 which will be in K4.

Hence answer is 4

Answer 6

Can i give reasoning like this ? @Akash Kanase 

The maximum complete graph with planarity is K4.

And to color K4 we need 4 vertices.

Now if we take 5 colors then it is also able to color K5 which is non planar.

Since we are only considering this for planar graphs the maximum number of colors we need is 4.