Théorème de VizingLe théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing. Une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. On note χ′(G) le nombre minimum de couleur nécessaire pour avoir une coloration des arêtes.
