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

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.

The graph K(3,2) or Complete Bipartite graph Is Planar But has a chromatic number 2 . Can some one tell me why the answer to this question is not 2 and is 4?

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 !

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.

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.

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

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

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

by
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.