A round-robin tournament has 8 teams, and each pair must play exactly once, with each team playing at most one game per round. What does the chromatic index of K₈ tell you?
AThe minimum number of games played in a single round
BThe total number of games in the tournament
CThe minimum number of rounds needed to complete the tournament
DThe maximum number of games any single team plays
Each color class in an edge coloring forms a matching — a set of games played simultaneously where no team appears twice. The chromatic index is the minimum number of matchings needed to cover all edges, which equals the minimum number of rounds. For K₈ (8 teams, n even), χ'(K₈) = 7 rounds. This scheduling interpretation is one of the primary practical applications of edge coloring.
Question 2 Multiple Choice
A graph has maximum degree Δ = 5. Vizing's theorem tells you that its chromatic index χ'(G) is:
AExactly 5 — the chromatic index always equals the maximum degree
BEither 5 or 6 — the chromatic index is always Δ or Δ+1
CBetween 1 and 5, depending on the specific structure
DAt least 5, with no tighter upper bound guaranteed
Vizing's theorem states that for any simple graph, χ'(G) ∈ {Δ, Δ+1}. The lower bound χ'(G) ≥ Δ is easy: all edges incident to a maximum-degree vertex need distinct colors. Vizing's remarkable result is that you never need more than Δ+1. Graphs achieving χ' = Δ are Class 1; those requiring Δ+1 are Class 2. Determining which class a given graph belongs to is NP-complete in general.
Question 3 True / False
In a valid edge coloring, all edges assigned the same color form a matching — a set of edges with no two sharing a vertex.
TTrue
FFalse
Answer: True
This follows directly from the edge coloring rule: no two edges sharing a vertex can have the same color. Therefore any two edges of the same color have no vertex in common — which is exactly the definition of a matching. An edge coloring is equivalent to partitioning all edges into matchings, and the chromatic index is the minimum number of matchings needed to cover every edge.
Question 4 True / False
Bipartite graphs usually require Δ+1 colors for edge coloring, making them Class 2 graphs.
TTrue
FFalse
Answer: False
This is the opposite of the truth. Bipartite graphs are always Class 1 — they require exactly Δ colors, never Δ+1. This is König's theorem. The difficulty lies in Class 2 graphs (those requiring Δ+1), and even determining whether an arbitrary graph is Class 1 or Class 2 is NP-complete.
Question 5 Short Answer
Why must the chromatic index of any graph be at least Δ, and what does Vizing's theorem add beyond this lower bound?
Think about your answer, then reveal below.
Model answer: The lower bound χ'(G) ≥ Δ follows directly: every edge incident to a maximum-degree vertex must receive a distinct color (since they all share that vertex), requiring at least Δ colors. Vizing's theorem adds the upper bound: you never need more than Δ+1. The answer always lies in {Δ, Δ+1} — but determining which value applies to a specific graph is NP-complete.
The lower bound is local (one high-degree vertex forces it); the upper bound is global (Vizing's proof shows the entire graph can always be edge-colored with Δ+1 colors via a careful recoloring argument). The stunning result is how tight this is: one extra color beyond the obvious lower bound is always enough, no matter how complex the graph.