An extension of Vizing's adjacency lemma on edge chromatic critical graphs

Vizing's adjacency lemma describes an important property of edge-chromatic critical graphs. In an edge-chromatic critical simple graph G of maximum degree Δ, if xy is an edge then x is adjacent with at least Δ - deg(y) + 1 vertices (≠y) of degree Δ. In this paper, we obtain an extension of this result to multigraphs. © 1999 Elsevier Science B.V. All rights reserved.