Questions: Vizing's Theorem

Question 1

A network engineer is scheduling data transfers between servers. Each server handles at most Δ = 8 simultaneous connections. She doesn't yet know whether the network graph is Class 1 or Class 2. What does Vizing's theorem guarantee?

• A. She will need exactly 8 time slots
• B. She will need exactly 9 time slots because most real-world graphs are Class 2
• C. She will need at most 9 time slots — the schedule can always be completed in Δ+1 = 9 slots or fewer
• D. Vizing's theorem does not apply to network scheduling problems

Answer: (C)

Vizing's theorem guarantees χ'(G) ≤ Δ+1 for any simple graph. Even without knowing whether the specific graph is Class 1 (needing 8 slots) or Class 2 (needing 9 slots), the engineer can guarantee the worst case requires at most 9 time slots. This upper bound is immediately useful for resource provisioning even before class membership is determined.

Question 2

Which of the following is always a Class 1 graph, requiring exactly Δ colors for edge coloring?

• A. Any graph with an odd number of vertices
• B. Complete graphs on an odd number of vertices (K₂ₙ₊₁)
• C. Any bipartite graph
• D. Odd cycles

Answer: (C)

Bipartite graphs are always Class 1 — this follows from König's edge-coloring theorem, which proves Δ colors always suffice for bipartite graphs. Odd cycles are Class 2: a 5-cycle has Δ = 2 but needs 3 colors since alternating colors on an odd-length cycle forces a conflict. Complete graphs on an odd number of vertices (K₂ₙ₊₁) are also Class 2.

Question 3

Vizing's theorem tells you exactly how many colors any specific graph needs for an optimal edge coloring.

• T. True
• F. False

Answer: False

Vizing's theorem narrows the chromatic index to exactly two possible values (Δ or Δ+1), but does not determine which value applies to a given graph. Determining class membership — deciding whether a specific graph is Class 1 or Class 2 — is NP-complete in general. Vizing's theorem gives a two-value bound, not an exact computation.

Question 4

Both bipartite graphs and complete graphs on an even number of vertices are Class 1 under Vizing's classification.

• T. True
• F. False

Answer: True

Bipartite graphs are always Class 1 by König's theorem. Complete graphs K₂ₙ on an even number of vertices are also Class 1 — their edges decompose into exactly Δ = 2n−1 perfect matchings, yielding a Δ-edge-coloring. This contrasts with K₂ₙ₊₁ (odd vertex count), which is Class 2.

Question 5

Vizing's theorem pins the chromatic index to one of two values. Why is this useful even though determining which value applies is NP-complete?

Model answer: The theorem provides a guaranteed upper bound: no matter the graph, χ'(G) ≤ Δ+1. In any scheduling or resource-assignment problem modeled as edge coloring, you know the worst case requires at most Δ+1 resources, even before determining whether Δ suffices. This upper-bound guarantee is immediately actionable for worst-case planning, even if minimizing to Δ when possible requires expensive computation.

Knowing the answer lies in {Δ, Δ+1} is far more useful than knowing only χ'(G) ≥ Δ — it transforms a potentially unbounded search into a binary question, even if that binary question is itself hard to resolve.