GATE CSE 2004 | Question: 77

Question

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

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Comments

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)

Answer 1

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

answer = option C

Comments

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.

---

@Hemant Parihar

Look, 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

---

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.

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

Ans C 

Answer 3

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

answer is C) 4 only

Comments

This is not a correct theorem/result.Counter ex: Degree of every vertex in Graph K₅ 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. 

Answer 4

short trick-

first eliminate option here 

according to 4 color theorm we cannot use more than 4 color 

so option (d) is wrong

Now, as you can see it contain cycle with odd n.o of edges i.e 3 

it means it contain atleast 3 colors

so option (a) is wrong

now we can easily check with 3 and 4 colors.