Question

State the four-color theorem. Are there graphs that cannot be colored with four colors?

Short answer

• Four- color theorem is the chromatic number of planar graphs should be at most 4.
• Yes, there graphs that cannot be colored with four-colors

Step-by-step solution

Step 1: The statement of four-color theorem

Four- color theorem is the chromatic number of planar graphs should be at most 4.

Step 2: Example of four-color theorem

• Take the example of a nonplanar graph k5.
• There are 5 vertices in this graph and all the vertices are adjacent to each other.
• In this graph, as all the 5 vertices cannot have the same color, there must be at least 4 colors required