# Théorème de Vizing

Le 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.

## Coloration des arêtes et borne inférieure

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.
On remarque que χ′(G) est forcement supérieure ou égal au degré maximum des nœuds (noté Δ), en effet toutes les arêtes adjacentes à ce nœud doivent avoir des couleurs différentes.

## Théorème

Le théorème stipule qu'étant donné un graphe G, le nombre χ′(G) est égal ou bien à Δ ou bien à Δ+1.
D'après la remarque de la section précédente, ce résultat est surtout important comme borne supérieure sur χ′.

## Exemple

* Un graphe où χ′(G)=Δ.
* Un graphe où χ′(G)=Δ+1.

## Démonstration

Montrons la propriété par récurrence sur le nombre d'arêtes du graphe G, noté m. Il s'agit donc de montrer qu'on peut colorer tout graphe à n sommets déterminés à l'avance avec au plus Δ+1 couleurs, où Δ est le degré maximal du graphe considéré.
* m = 0 :
Un graphe à 0 arête peut se colorer avec une couleur.
* m = m'+1 :
Supposons la propriété vraie pour un entier m quelconque, et montrons qu'elle reste vraie pour l'entier m+1. Soit G un graphe à m'+1 arêtes. Enlevons une arête μ de ce graphe. On obtient un graphe G à m arêtes dont on peut colorer les arêtes, d'après l'hypothèse de récurrence. Essayons à présent de « remettre » μ dans G' pour obtenir à nouveau le graphe G.
On appellera A et B$_1$ les sommets initialement reliés par l'arête μ.
Nécessairement, puisque A est de degré inférieur ou égal à Δ, il existe une couleur parmi les Δ+1 disponibles qui n'est pas utilisée pour colorer les arêtes incidentes au sommet A. De même, il existe une couleur parmi les Δ+1 qui n'est pas utilisée pour la coloration des arêtes de B$_1$.
      * Cas 1 :
Si on peut trouver une couleur non utilisée à la fois pour la coloration des arêtes adjacentes à A et pour la coloration des arêtes adjacentes à B$_1$, alors il suffit de choisir cette couleur pour μ et de replacer cette arête une fois colorée à son emplacement initial dans G.
      * Cas 2 :
Si les couleurs manquant à A sont présentes au sommet B$_1$ et réciproquement, notons a une des couleurs manquant à A et b$_1$ une couleur manquant à B$_1$. Examinons la chaîne de Kempe associée aux couleurs a et b$_1$ et partant de B$_1$ : H(a,b$_1$). Si cette chaîne ne relie pas B$_1$ à A, on échange les deux couleurs dans cette chaîne (les arêtes du graphe G' restent ainsi correctement colorées) puis on choisit la couleur a pour μ et on replace cette arête à son emplacement initial.
      * Cas 3 :
Si en plus de ne pouvoir trouver une couleur manquant à A et à B$_1$, la chaîne de Kempe H(a,b$_1$) relie ces deux sommets, on effectue les opérations suivantes :
* on identifie l'arête de couleur b$_1$ incidente à A (appelons la μ') et on appelle B$_2$ le sommet à l'autre extrémité de l'arête en question.
* on extrait cette même arête d'entre A et B$_2$ pour la placer entre A et B$_1$. μ' est à présent l'arête que l'on doit replacer pour obtenir à nouveau le graphe G.
Il faut alors procéder comme précédemment pour trouver la couleur adéquate avec laquelle colorer μ'. Il se peut que l'on revienne à chaque fois dans le « cas 3 ».
Au bout d'un certain temps (Δ fois au maximum), il arrive donc que la couleur manquant au sommet B$_i$ ait déjà été la couleur manquant à un sommet B$_k$ (k<i). Notons que l'on a même k < i-1 étant donné que l'on vient juste de retirer la couleur b$_{i-1}$ au sommet B$_i$.
Ainsi on a une chaîne de Kempe H(a,b$_k$) qui part de A, qui rejoint B$_{k+1}$, et dont les sommets ont tous la couleur b$_k$ (sauf B$_{k+1}$ puisqu'on a justement retiré l'arête de couleur b$_k$ adjacente à ce somment pour la mettre entre B$_k$ et A. On a vu que B$_i$ n'avait pas d'arête adjacente de couleur b$_k$, partant de quoi on affirme que B$_i$ n'est pas sur la chaîne de Kempe H(a,b$_k$) que l'on vient de mentionner.
D'autre part, on sait que le sommet B$_i$ a une arête adjacente de couleur a et que de ce fait il appartient à une autre chaîne de Kempe H'(a,b$_k$), disjointe de la chaîne H(a,b$_k$) (H'(a,b$_k$) peut être réduite à une simple arête de couleur a). Il suffit alors d'intervertir les couleurs des arêtes de H'(a,b$_k$) et de relier B$_i$ et A avec un arête de couleur a pour ainsi reconstruire le graphe G coloré (lors de cette dernière opération, on aura relié les chaînes H(a,b$_k$) et H'(a,b$_k$) ).