GATE 2016 CS (CS2) – Question 13

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer

Find the minimum number of colours sufficient to vertex-colour every planar graph.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 4.0 to 4.0

Explanation

The four-colour theorem guarantees at most four colours for every planar graph. The planar complete graph K₄ needs four because every pair of vertices is adjacent. Thus four is both sufficient and sometimes necessary: answer 4.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2016 CS (CS2) Q38 – There are 23 distinct compounds U. Each of nine compounds in S reacts with exactly three…
GATE 2017 CS (CS2) Q33 – An undirected graph has n vertices, 25 edges and every vertex has degree at least three.…
GATE 2012 CS (CS1) Q27 – A connected simple planar graph has ten vertices and fifteen edges. How many bounded faces…
GATE 2012 CS (CS1) Q36 – Which graph A,B,C,D is isomorphic to the given graph?
GATE 2013 CS (CS1) Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all…
GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →