Exams › GATE › Engineering Mathematics

The minimum number of colours that is sufficient to vertex-colour any planar graph is

1. 2
2. 3
3. 4
4. 5

Correct answer: 4

Solution

According to the Four Color Theorem, any planar graph can be colored using no more than four colors such that no two adjacent vertices share the same color, making four the minimum sufficient number for vertex-coloring any planar graph.

Related GATE Engineering Mathematics questions

• What are the eigenvalues of the matrix [2, 1, 1; 1, 4, 1; 1, 1, 2]?
• A circle with center at (x,y) = (0.5, 0) and radius = 0.5 intersects with another circle with center at (x,y) = (1,1) and radius = 1 at two points. One of the points of intersection (x,y) is:
• Suppose λ is an eigenvalue of matrix A and x is the corresponding eigenvector. Let x also be an eigenvector of the matrix B = A − 2I, where I is the identity matrix. Then, the eigenvalue of B corresponding to the eigenvector x is equal to
• Let A = [[1, 1], [1, 3], [−2, −3]] and b = [b1, b2, b3]. For Ax = b to be solvable, which one of the following options is the correct condition on b1, b2, and b3:
• If the quadrantal bearing of a line is N 30° W, then the whole circle bearing of the line is
• The matrix [2, -4; 4, -2] has

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →