Graph G contains a complete subgraph K₄ (four mutually adjacent vertices). What can you immediately conclude about the chromatic number χ(G)?
Aχ(G) = 4, because K₄ forces exactly four colors
Bχ(G) ≥ 4, because the K₄ subgraph alone requires four distinct colors
Cχ(G) ≤ 4, because planar graphs need at most four colors
Dχ(G) = Δ(G) + 1, because the maximum degree determines the chromatic number
The clique number ω(G) provides a lower bound: χ(G) ≥ ω(G). Since K₄ is a clique of size 4, all four vertices are mutually adjacent and must each receive a distinct color — so at least 4 colors are needed. But χ(G) could be larger than 4 if the rest of the graph forces more colors. Option A is too strong: the clique gives a lower bound, not an exact value. The Four Color Theorem (option C) applies to planar graphs, but G may not be planar.
Question 2 Multiple Choice
Five tasks (A, B, C, D, E) must be scheduled into time slots. Conflicts exist between A–B, B–C, C–D, D–E, and A–E (forming a 5-cycle, C₅). What is the minimum number of time slots needed?
A2 — since no three tasks all conflict with each other
B3 — a 5-cycle contains no triangle but cannot be 2-colored
C5 — each task needs its own slot because the cycle has no independent set
D4 — the maximum degree is 2, so Δ + 1 = 3 is insufficient
A 5-cycle (odd cycle) cannot be properly 2-colored: starting with color 1 on A, alternating forces color 1 on both D and E, but A and E conflict. Three colors suffice: color A=1, B=2, C=1, D=2, E=3. The largest clique in C₅ has size 2 (any edge), so ω = 2, but χ = 3 — demonstrating that the chromatic number can exceed the clique number.
Question 3 True / False
The greedy coloring algorithm usually finds the minimum number of colors needed to properly color a graph.
TTrue
FFalse
Answer: False
Greedy coloring is not optimal in general. It produces a valid proper coloring using at most Δ(G) + 1 colors, but the result depends on the order vertices are processed. For some orderings it may use more colors than χ(G). For example, a bipartite graph has χ = 2, but a greedy coloring in a bad vertex order could use more than 2. Greedy provides an upper bound on χ(G), not the exact value.
Question 4 True / False
The chromatic number χ(G) of a graph is generally equal to the size of its largest clique ω(G).
TTrue
FFalse
Answer: False
This is false in general. The clique number ω(G) gives a lower bound — χ(G) ≥ ω(G) — but χ can be strictly larger. A famous example is the Mycielski graphs: they have ω = 2 (no triangle) but arbitrarily high chromatic number. For odd cycles Cₙ (n ≥ 5), ω = 2 but χ = 3. The gap between ω and χ reveals that graph coloring is not reducible to clique detection.
Question 5 Short Answer
What does the chromatic number χ(G) measure, and why does the clique number ω(G) provide a lower bound for it?
Think about your answer, then reveal below.
Model answer: The chromatic number χ(G) is the minimum number of colors needed to assign colors to all vertices so that no two adjacent vertices share a color. The clique number ω(G) is the size of the largest complete subgraph (clique). In any clique, every vertex is adjacent to every other, so all vertices in the clique must receive distinct colors. Therefore the clique alone forces at least ω(G) colors to be used, making ω(G) a lower bound for χ(G).
The lower bound argument is tight and clean: a clique of size k is a subgraph that by itself requires k colors, so χ(G) ≥ k for any k-clique G contains. The upper bound comes from greedy: χ(G) ≤ Δ(G) + 1. The actual chromatic number lies somewhere in the range [ω(G), Δ(G)+1], and determining the exact value is NP-hard in general.