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

this may be silly but how we know that the given graph is planar @Bikram sir?

---

@pavansan  We say that graph is planar if the given graph does not have any cross edge. and if graph have cross edge then we try to make it planar by changing it's edge representation.

See this image K4 is complete graph and have cross but we can remove cross edge by changing it's representation see conversion. 

NOTE: If we cannot convert given graph to it's planar representation then that graph is not planar see below image.

By any means we cannot represent K5 and K3,3 in planar graph. That means these graph are not planar. 
The given graph in question is planar since it does not have any cross edges. 

---

@Kishan Songara yeah thanks now understood 

Answer 1

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

answer = option C

Comments

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

 

---

Four color theorem states that

For any planar graph, the chromatic number is ATMOST  4

So, we dont have to check for 5.

Also there is a triangle in graph (ie, cycle of length 3). So, Chromatic number can't be 2. 

It's either 3 or 4.

If we try with 3 then we won't be able to color all vertices. So minimum 4 colors are required.

 

See this for reference. And this GATE PYQ

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. 

---

The answer is correct according to Brooke's theorem which states that for a connected graph the chromatic number <=max degree of the graph except for odd and complete graph it is atmost max degree of graph +1

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.

Answer 5

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

Answer 6

Since the graph is planar graph it is 4 colorable.

Comments

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