Question

What is the Four Colour Theorem?

• A. The chromatic number of a wheel graph is no greater than four
• B. The chromatic number of a planar graph is no greater than four
• C. The chromatic number of a bipartite graph is no greater than four
• D. The chromatic number of a planar graph is equal to four

Hint:

Four Colour Theorem: \[ \chi(G)\le4 \] for every planar graph \(G\). Remember: "At most four colors", not necessarily exactly four.

Answer 1

The Correct Option is B

Concept: The Four Colour Theorem is one of the most famous results in graph theory. It states that every planar graph can be colored using at most four colors so that no two adjacent vertices (or regions) receive the same color. Historically, this theorem was the first major theorem proved using extensive computer assistance.

Step 1: Understand planar graphs.
A planar graph is a graph that can be drawn in a plane without any edges crossing each other. Examples include many map-coloring problems.

Step 2: Recall the statement of the theorem.
The theorem says: \[ \chi(G)\le4 \] for every planar graph \(G\), where \(\chi(G)\) denotes the chromatic number.

Step 3: Interpret the result.
This means four colors are always sufficient. Some planar graphs may require fewer than four colors. Therefore the theorem says "at most four colors" and not "exactly four colors."

Step 4: Select the correct option.
Hence, \[ \boxed{\text{The chromatic number of a planar graph is no greater than four}} \] which corresponds to option (B).