edited by
15,317 views
43 votes
43 votes
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
edited by

4 Answers

Best answer
70 votes
70 votes

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 !

edited by
7 votes
7 votes

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

                              answer is 4

edited by
4 votes
4 votes
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:

Related questions

50 votes
50 votes
4 answers
4
Akash Kanase asked Feb 12, 2016
17,628 views
The width of the physical address on a machine is $40$ bits. The width of the tag field in a $512$ KB $8$-way set associative cache is ________ bits.