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

Option C is correct
We need 4 colors required to color vertices of the graph.

Answer 2

Since the graph is planar graph it is 4 colorable.

Comments

Planar graphs can be less than 4 colorable as well.

---

raja11sep

any example bro?

---

@Pranavpurkar Take 2 vertices and connect them with a edge. It's 2 colorable. Many examples are there.

---

raja11sep

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

 

---

raja11sep

see this comment once → https://gateoverflow.in/1071/Gate-cse-2004-question-77?show=374106#c374106

Answer 3

The max degree of the vertex is 4 so we need atleast 5 colours to colour the graph

Comments

4 colours are enough here !

---

It is a planar graph so we need only 4 colour.

---

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

But here d+1 is not the min value.