GATE CS 2016 Set 2 Q.13 (CS Q.3): Graph Theory

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

Your answer

Official answer and solution

Official answer: 4
From: Official GATE 2016 answer key

Solution

Apply the Four Color Theorem for vertex coloring of planar graphs.

The Four Color Theorem states that the vertices of every planar graph can be colored using at most 4 colors such that no two adjacent vertices share the same color.

Furthermore, the complete graph on 4 vertices ( $K_4$ ) is planar and requires exactly 4 colors because every pair of vertices is connected by an edge.

Therefore, the minimum number of colors that is sufficient to vertex-color any planar graph is 4.

Final answer

Common trap

Confusing vertex coloring (4 colors) with edge coloring (Vizing's theorem) or thinking 5 colors because of the easier 5-color theorem.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 13 of 65, printed as CS Q.3
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source