GATE DA 2024 Set 1 — Question 2
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+1 / -0.33MediumSpatial AptitudeGeneral Aptitude2D & 3D Patterns
General Aptitude → Spatial Aptitude → 2D & 3D Patterns
Last updated
Question
The 15 parts of the given figure are to be painted such that no two adjacent parts with shared boundaries (excluding corners) have the same color. The minimum number of colors required is
Correct answer
(A) 4
Solution
The problem asks for the minimum number of colors required to paint the regions of the given planar map such that no two adjacent regions share the same color. This is a classic map coloring problem.
Visually, the central 3 regions use colors {1, 2, 3}. The regions surrounding them must alternate colors to avoid touching the center and each other. Due to the odd number of central sectors and the connectivity of the outer rings, a 4th color becomes necessary to resolve the conflicts at the boundaries.Therefore, the minimum number of colors required is 4.
1.Upper Bound (Four Color Theorem): The Four Color Theorem states that any separation of a plane into contiguous regions can be colored using no more than 4 colors. Since the given figure is a planar map, the maximum number of colors required is at most 4. This eliminates options (C) and (D).
2.Lower Bound (Necessity of 4 colors): We need to check if 3 colors are sufficient. The figure contains a central circle divided into 3 sectors that all touch each other at the center point. These 3 regions are mutually adjacent, forming a (triangle) in the dual graph, requiring at least 3 colors.
Surrounding these central sectors, the arrangement of the adjacent regions creates constraints. Specifically, if we attempt to color the map with 3 colors, we will encounter a conflict. The adjacency structure effectively contains an 'odd wheel' or a configuration equivalent to a (four mutually adjacent regions) or a subgraph that cannot be 3-colored (like the Moser spindle configuration embedded in the adjacencies).Visually, the central 3 regions use colors {1, 2, 3}. The regions surrounding them must alternate colors to avoid touching the center and each other. Due to the odd number of central sectors and the connectivity of the outer rings, a 4th color becomes necessary to resolve the conflicts at the boundaries.Therefore, the minimum number of colors required is 4.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE DA question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Spatial Aptitude
2026 Set 1 Q1Verbosity : Brevity :: Insolence :___________ Choose the word that best fills the blank.2026 Set 1 Q2The product of the digits of a three-digit number is 70. The sum of the digits of this three-digit…2026 Set 1 Q3The four pieces of a puzzle are shown in the figure below. [figure] Which one of the figures…2026 Set 1 Q4Consider two distinct positive real numbers , with . Let and…2026 Set 1 Q5‘If his latest movie had been a commercial success, the actor would have made enough money to…