Questions: Graph Coloring and the Chromatic Number

Question 1

What is the chromatic number of the cycle graph C₅ (a pentagon — 5 vertices in a single cycle)?

• A. 2
• B. 3
• C. 4
• D. 5

Answer: (B)

Odd cycles require 3 colors. Try 2-coloring C₅: alternate colors around the cycle, but the 5th vertex is adjacent to both the 4th vertex and the 1st, which have different colors — yet both colors are already used by its neighbors. A 3-coloring works: assign color 1, 2, 1, 2, 3 around the pentagon. Even cycles (C₄, C₆, …) are bipartite and need only 2 colors.

Question 2

The chromatic number of any graph equals the size of its largest clique.

• T. True
• F. False

Answer: False

The clique number ω(G) is always a lower bound for χ(G) — a clique of size k requires k colors — but it is not always tight. The Mycielski construction produces graphs that are triangle-free (ω = 2) yet have arbitrarily large chromatic number. This shows that the global coloring structure of a graph can force many colors even without any large complete subgraph.

Question 3

To prove that χ(G) = k for some specific graph G, what two things must you demonstrate?

Model answer: You must show (1) that a valid k-coloring exists, establishing χ(G) ≤ k, and (2) that no valid (k−1)-coloring exists, establishing χ(G) ≥ k. Together, the upper and lower bounds pin down χ(G) = k exactly.

This two-part structure — an explicit construction for the upper bound and an impossibility argument for the lower bound — is the standard proof template for chromatic number. The lower bound often uses a large clique, an odd cycle, or a counting/pigeonhole argument.