Every simple graph has edge chromatic number χ'(G) ∈ {Δ, Δ+1} where Δ is the maximum degree. Class-1 graphs attain Δ (e.g. K_n for n even); class-2 graphs need Δ+1 (e.g. K_n for n odd). Deciding class-1 vs. class-2 is NP-complete.
Every simple graph has edge chromatic number χ'(G) ∈ {Δ, Δ+1} where Δ is the maximum degree. Class-1 graphs attain Δ (e.g. K_n for n even); class-2 graphs need Δ+1 (e.g. K_n for n odd). Deciding class-1 vs. class-2 is NP-complete.