In a heptagon (7-sided polygon) ABCDEFG, a triangle BDF is drawn. Arafa is coloring the vertices under the condition that no edge will have the same colored vertices. What is the minimum number of different colors to be used? A. 6 B. 5 C. 4 D. 3
1 Answer
D.
Explanation:
Three colours are sufficient.
Given:
Attempting to use just three colours, we can proceed as follows:
-
Colour vertex B red.
-
Colour vertex C green since it must be different from B.
-
Colour vertex D blue since it must be different from B and C.
-
Colour vertex F green since it must be different from B and D.
-
Colour vertex E red since it must be different from D and F.
-
We can then colour vertex A blue to be different from B (green would be ok too).
-
We can then colour vertex G red.
So three colours are sufficient...
Footnote
In general for any planar, non-crossing graph, four colours will always be sufficient. This is extremely difficult to prove. The first correct proof was found by Kenneth Appel and Wolfgang Haken in 1976, but required a computer to generate and check it. To prove that five colours is always sufficient is much easier and is often given as an exercise to students.
