Vizing's Theorem

Graph Theory · Axiom Academy

Understanding the fundamental bounds on edge chromatic number For any simple graph G with maximum degree Δ(G), the edge chromatic number satisfies: This means every graph needs either exactly Δ(G) colors or Δ(G) + 1 colors to properly color its edges. There are no graphs that need more than Δ(G) + 1 colors! Δ(G) : Maximum degree (highest number of edges at any vertex) χ'(G) : Edge chromatic number (minimum colors needed for edge coloring) Graphs where the edge chromatic number equals the maximum degree are called Class 1 graphs . All bipartite graphs (by König's Theorem) Complete graphs K n where n is even Watch the animation below to see a bipartite graph K 3,3 being edge-colored with exactly Δ = 3 colors: Graphs where the edge chromatic number is one more than the maximum degree are called Class 2 graphs . Complete graphs K n where n is odd (e.g., K 3 , K 5 ) Many graphs with odd cycles and high density Watch the animation below to see K 5 (complete graph on 5 vertices) being edge-colored. It has Δ = 4, but needs 5 colors: 4. Class 1 vs Class 2: Visual Comparison Let's directly compare a Class 1 graph (cycle C 6 ) with a Class 2 graph (complete graph K 3 ) to understand the difference: Key Insight: Class 2 graphs have a "tight" structure where edges compete more intensely for colors. Class 1 graphs have enough structural "slack" to be colored optimally. Vizing's proof is constructive and uses a clever technique called Kempe chain recoloring .

This is the written version of the interactive lesson above. See the full Graph Theory course.