9,730 views

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

1. $2$
2. $3$
3. $4$
4. $5$

graph is planar so we can directly say it requires not more than 4 color

this graph has also odd length cycle for that 3 color requires

also this graph has even length cycle for that 2 color

but i have a doubt here :

if graph is very complex and if both the even and odd length cycle appears as well as planar solution then whts the correct aproach to find color requirement in graph

same situation with this https://gateoverflow.in/3263/gate2008-it-3

@Bikram sir which approach ?pls help

The chromatic number of a planar graph is no more than four.

We can use this approach here.

as it is maximum 4 , then 4 colors require for complex kind of graphs where both the even and odd length cycle appears as well as planar solution ..

Please let me know where i am getting wrong. !!

Two adjacent vertex have got same color (C1)

$4$ colors are required to color the graph in the prescribed way.

So we know four color theorem which say any planar graph will be 4 colorable. So this graph is planar so max color required will be 4. Now to strect it you take 3 color and try to color every vertices and you will find definetely 3 is not enough in here so answer is 4.

Look, Theorem 5.10.6 (Five Color Theorem)

Every planar graph can be colored with 5 colors.

edited

ASNR1010

bro so its 4 or 5 now?

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

Ans C

by
note:-The max degree of the vertex is 4 so we need atmost 4 colours to colour the graph

### 1 comment

This is not a correct theorem/result.Counter ex: Degree of every vertex in Graph K5 is 4 (max degree is 4) but we need 5 colors to color the graph.

correct theorem: If every vertex in G has degree at most d then G admits a vertex coloring using d+1 colors.

Since the graph is planar graph it is 4 colorable.

so is it like this that every planar graph can be colored with a maximum of 4 colors and not more than that?

@Pranavpurkar for any graph with v vertices , we can color it by v color but here we are talking about chromatic number means coloring by minimum color possible.

chromatic number of any planar graph can not be more than 4