GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes
The minimum number of colours that is sufficient to vertex-colour any planar graph is ______________
asked in Graphs by gate

1 Answer

0 votes

If we talk about minimum no. of colors that is sufficient to vertex-color in any planar graph which means a planar graph with any no. of vertices. However, in some cases, 3 colors are suffcient to vertex-color in a planar graph like triangle whereas in some cases 4 colors are suffcient to vertex-color in a planar graph . But is has been proved that 4 colors are sufficient to vertex-color every planar graph. It is called as the four color theorem. So, the answer will be 4.

answered by manju bhatt

Related questions

The best answer to any question