Vizing's theorem

In graph theory, Vizing's theorem (named for Vadim G. Vizing who published it in 1964) states that the edges of every simple undirected graph may be colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph.

At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary.

When $Δ = 1$ , the graph $G$ must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with $Δ(G) = 1$ are of class one.

When $Δ = 2$ , the graph $G$ must be a disjoint union of paths and cycles. If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. That is, a graph with $Δ = 2$ is of class one if and only if it is bipartite.

Multigraphs do not in general obey Vizing's theorem. For instance, the multigraph formed by doubling each edge of a triangle has maximum degree four but cannot be edge-colored with fewer than six colors.

This proof is inspired by Diestel (2000).

Let $G = (V, E)$ be a simple undirected graph. We proceed by induction on $m$ , the number of edges. If the graph is empty, the theorem trivially holds. Let $m > 0$ and suppose a proper $(Δ+1)$ -edge-coloring exists for all $G - xy$ where $xy \in E$ .

We say that color $α \in {1,...,Δ+1$ } is missing in $x \in V$ with respect to proper $(Δ+1)$ -edge-coloring $c$ if $c (xy) \neq α$ for all $y \in N(x)$ . Also, let $α/β$ -path from $x$ denote the unique maximal path starting in $x$ with $α$ -colored edge and alternating the colors of edges (the second edge has color $β$ , the third edge has color $α$ and so on), its length can be $0$ . Note that if $c$ is a proper $(Δ+1)$ -edge-coloring of $G$ then every vertex has a missing color with respect to $c$ .

...
Wikipedia