History In both and , Vizing mentions that his work was motivated by a theorem of showing that multigraphs could be colored with at most colors. Although Vizing's theorem is now standard material in many graph theory textbooks, Vizing had trouble publishing the result initially, and his paper on it appears in an obscure journal, Diskret. Analiz. See also Brooks' theorem relating vertex colorings to maximum degree Notes References . . . . . . . . . . . . . . . . (In Russian.) . External links Proof of Vizing's theorem at PlanetMath. Graph coloring Theorems in graph theory