It is little bit language problem. Just read the comment given below the selected answer.

Dark Mode

11,561 views

36 votes

5

0

65 votes

Best answer

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.

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

0

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

0

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

0

6 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 vertice**s (k _{4})**

it requires **minimum 4 colours **

6)cosider a complete graph of 5 vertice**s (k _{5})**

it requires * minimum 5 colours with respect to vertex colour , but k_{5 }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*

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.