GATE CSE 2016 Set 2 | Question: 03

Question

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

Comments

because they are asking minimum number and the best planar graph is K4 and four colour therom says the minimum colours can be filled are 4

---

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

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

Interestingly, the original four color theorem was about coloring the regions of a planar graph. Narsingh Deo states that a graph has a dual if and only if it is planar, therefore coloring regions of a planar graph $G$ is equivalent to coloring the nodes of its dual $G^*$, and vice versa.

So the four color theorem can also be restated in terms of nodes instead of regions.

---

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)!

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.