Question
Download Solution PDFThe minimum number of colours that is sufficient to vertex-colour any planar graph is_______.
Answer (Detailed Solution Below) 4
Detailed Solution
Download Solution PDFConcept:
A planar graph is a graph in which no two edges cross each other. A vertex coloring of a graph is an assignment of colors to the vertices of graph such that adjacent vertices have different colors.
Explanation:
According to the property of planar graph and four colour theorems. Maximum number of colours that are needed to vertex-colour any planar graph is 4.
Example:
In this graph, only 3 colours are enough to colour this planar graph.
But if in this graph, there is an edge from a to d also, then three colours are not enough to vertex-colour this graph.
In this graph, 4 colours are needed to vertex- colour this graph.
Last updated on Jan 8, 2025
-> GATE CS 2025 Admit Card has been released on 7th January 2025.
-> The exam will be conducted on 1st February 2025 in 2 shifts.
-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.
-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.
-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.