GATE DS&AI 2024 | GA Question: 2

Question

​​​​​​The $15$ parts of the given figure are to be painted such that no two adjacent parts with shared boundaries (excluding corners) have the same color. The minimum number of colors required is

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

Answer 1

A. 4

four color theorem

https://uu.diva-portal.org/smash/get/diva2:749857/FULLTEXT01.pdf

Answer 2

How answer is A, can anyone explain?

Comments

try coloring the graph from the inner circle.

Answer 3

4

Answer 4

A. 4 

We can't color with using only 3 colors.

As given graph is planar so minimum no. of colors required to  is 4.

Well known four color theorem says "every planar graph is four-colorable".

https://en.wikipedia.org/wiki/Four_color_theorem