Questions: Edge Coloring and Vizing's Theorem

Question 1

A graph G has maximum degree Δ(G) = 7. According to Vizing's theorem, what are the only possible values of the chromatic index χ'(G)?

• A. Any integer from 1 to 7
• B. Exactly 7 or exactly 8
• C. Exactly 7 (since bipartite graphs always achieve the lower bound)
• D. At most 14 (since the theorem guarantees χ'(G) ≤ 2Δ)

Answer: (B)

Vizing's theorem states that for any simple graph, χ'(G) ∈ {Δ(G), Δ(G)+1}. With Δ = 7, the chromatic index must be exactly 7 (Class 1) or exactly 8 (Class 2) — no other values are possible. This tight two-outcome result is the remarkable content of the theorem: despite no obvious reason why it should be so constrained, the chromatic index never exceeds the obvious lower bound by more than 1.

Question 2

An employee scheduling problem models workers as vertices and required meetings between pairs of workers as edges. Each meeting needs a time slot, and two meetings sharing a worker cannot occupy the same slot. After modelling this as a graph with maximum degree Δ = 5, a manager claims the schedule can always be completed in 5 or 6 time slots. What justifies this claim?

• A. König's theorem guarantees that scheduling graphs are always bipartite and therefore require only Δ slots
• B. Vizing's theorem guarantees χ'(G) ∈ {Δ, Δ+1} for any simple graph, so the minimum slots needed is either 5 or 6
• C. The chromatic polynomial shows that any graph with Δ = 5 requires exactly 5 colors for a proper edge coloring
• D. Vertex coloring with 5 colors implies edge coloring with 5 colors by a standard reduction

Answer: (B)

Vizing's theorem converts the unbounded question 'how many time slots?' into the binary question 'are Δ slots enough, or do we need Δ+1?' For any scheduling graph with Δ = 5, we are guaranteed that 6 slots always suffice and 5 may suffice. Option A is true for bipartite graphs specifically (König's theorem) but cannot be asserted for general graphs. Option D reflects the common misconception that vertex and edge coloring are closely related — they are different problems with different bounds.

Question 3

Because Vizing's theorem constrains the chromatic index to mainly two possible values, determining which value applies to a given graph is computationally tractable in polynomial time.

• T. True
• F. False

Answer: False

This is the central surprise: despite the output being binary (Class 1 or Class 2), deciding which class a graph belongs to is NP-complete in general. A narrow answer space does not imply computational ease. This is a recurring theme in graph theory: the difficulty of a problem is not determined by the size of its output space. Vizing's theorem is valuable because it bounds the answer, not because it makes finding the answer easy.

Question 4

All bipartite graphs are Class 1, meaning their chromatic index equals their maximum degree Δ.

• T. True
• F. False

Answer: True

This is König's edge coloring theorem: for bipartite graphs, χ'(G) = Δ(G). Bipartite structure prevents the 'bottlenecks' that force Class 2 graphs to need an extra color. This is why scheduling problems modeled as bipartite graphs (e.g., tasks on one side, machines on the other) can always be solved optimally with Δ slots. Non-bipartite graphs — including odd cycles, complete graphs Kₙ for odd n, and the Petersen graph — may be Class 2.

Question 5

Why is it surprising that determining a graph's class (Class 1 vs. Class 2) is NP-complete, given that the chromatic index can only be one of two values?

Model answer: Intuitively, a problem with only two possible outputs should be easy — it seems like a yes/no question. But NP-completeness captures the difficulty of verifying or constructing the coloring that witnesses the answer, not just the size of the answer space. Even knowing χ'(G) ∈ {Δ, Δ+1}, we have no known polynomial-time algorithm for determining which value applies, because the structural properties that force Class 2 membership (like the presence of certain subgraph configurations) are globally complex to detect. This contrasts with, say, checking bipartiteness (easy), which immediately guarantees Class 1.

This observation also highlights the value of special cases: for bipartite graphs (König's theorem) and regular graphs (Vizing-type results), classification is tractable. The NP-hardness applies in general, which means practical edge-coloring algorithms often rely on graph-specific structure. Vizing's theorem is still useful as an upper bound guarantee even without knowing the exact class — you can always build a valid coloring with Δ+1 colors in polynomial time.