Questions: Graph Coloring and Chromatic Numbers

Question 1

Graph G contains a triangle (three mutually adjacent vertices) as a subgraph. What can you conclude about χ(G)?

• A. χ(G) = 2, since most graphs are bipartite and 2-colorable
• B. χ(G) = n, where n is the number of vertices in G
• C. χ(G) ≥ 3, since the three mutually adjacent vertices of the triangle each require a different color
• D. χ(G) ≤ 3, since the four-color theorem guarantees any graph needs at most 4 colors

Answer: (C)

A triangle (K₃) has three vertices that are all pairwise adjacent — each pair shares an edge and so must receive different colors. This forces at least 3 colors for those vertices alone, so χ(G) ≥ 3. The four-color theorem (option D) applies only to planar graphs, not all graphs. The general principle: the chromatic number of any graph is at least as large as its largest clique (complete subgraph).

Question 2

You run a greedy coloring algorithm on graph G and use 5 colors. Your friend claims to have found a valid coloring of G using only 4 colors. Is this a contradiction?

• A. Yes — greedy coloring always finds the minimum number of colors, so χ(G) = 5
• B. No — greedy coloring gives an upper bound but doesn't guarantee optimality; χ(G) could be 4 or even fewer
• C. Yes — if a 4-coloring existed, the greedy algorithm would have found it
• D. No — but χ(G) must be exactly the average of 4 and 5, since both are valid

Answer: (B)

Greedy coloring produces a valid coloring but not necessarily a minimum one. The order in which vertices are processed affects the result, and a poor ordering can waste colors. The greedy bound χ(G) ≤ Δ(G) + 1 guarantees termination but is often not tight. Your friend's 4-coloring proves χ(G) ≤ 4, which is a better upper bound. The true chromatic number is the minimum over all valid colorings — greedy can only approach it from above.

Question 3

Every bipartite graph has a chromatic number of exactly 2.

• T. True
• F. False

Answer: True

A bipartite graph has vertices split into two independent sets — no two vertices within the same set share an edge. Assign color 1 to all vertices in one set and color 2 to all vertices in the other set. Since every edge goes between the two sets, adjacent vertices always receive different colors. This is a valid 2-coloring. And since a bipartite graph has at least one edge, it cannot be 1-colored. So χ(G) = 2 exactly. Conversely, if χ(G) = 2, the two color classes form a bipartition, so G is bipartite — bipartiteness and χ = 2 are equivalent.

Question 4

The four-color theorem guarantees that any graph, regardless of structure, can be properly colored with at most 4 colors.

• T. True
• F. False

Answer: False

The four-color theorem applies specifically to planar graphs — graphs that can be drawn in the plane without edge crossings. For non-planar graphs, the chromatic number can be arbitrarily large. For example, the complete graph Kₙ requires n colors, and complete graphs with n ≥ 5 are non-planar. A common misconception is extending the theorem beyond its planar constraint, but the theorem says nothing about non-planar graph colorability.

Question 5

Why is computing the chromatic number χ(G) of an arbitrary graph computationally hard, even though verifying whether a given coloring is proper is easy?

Model answer: Verifying a coloring requires only checking each edge to confirm its two endpoints have different colors — a linear-time scan. But computing χ(G) requires finding the minimum k such that a valid k-coloring exists, which means determining whether a k-coloring exists for k = 1, 2, 3, … in turn. Deciding whether a graph has a valid k-coloring (for k ≥ 3) is NP-complete, meaning no polynomial-time algorithm is known. The gap between easy verification and hard search is the hallmark of NP-hard problems, and graph coloring is one of the classic examples.

This easy-to-verify, hard-to-compute structure is why graph coloring models genuinely difficult real-world problems: exam scheduling, register allocation in compilers, and frequency assignment in wireless networks are all NP-hard optimizations. In practice, one establishes bounds (clique size ≤ χ ≤ Δ+1) and uses heuristics or approximations.