Vizing’s Theorem and Its Sharp Bound

Two Possible Values for the Edge Chromatic Number

In a proper edge coloring, edges that share an endpoint must receive different colors. The edges of any one color therefore form a matching: a set of edges no two of which share a vertex. This restriction immediately gives a lower bound on the number of colors, since all edges incident with a vertex must have different colors. The surprising part is that for a finite simple graph this lower bound misses the answer by at most one.

We will use $\chi'(G)$ for the edge chromatic number of $G$, the minimum number of colors in a proper edge coloring, and $\Delta(G)$ for its maximum degree. Graphs in this tutorial are finite and simple. If a graph has no edges, we set $\chi'(G)=0$; this convention handles the edgeless graph separately from the usual statement of Vizing’s theorem.

Definition: A proper edge coloring of a graph $G=(V,E)$ assigns a color to each edge so that any two distinct edges with a common endpoint have different colors. The edge chromatic number $\chi'(G)$ is the least number of colors in a proper edge coloring. A graph with at least one edge is class one if $\chi'(G)=\Delta(G)$, and class two if $\chi'(G)=\Delta(G)+1$.

For graphs with at least one edge, $\Delta(G)\geq 1$, so these two possibilities are distinct. Calling a graph class one or class two describes its edge-coloring requirement; it does not mean that every graph of a given maximum degree belongs to the same class.

The Lower Bound from a Vertex

Proposition: For every graph $G$ with at least one edge, $\chi'(G)\geq\Delta(G)$.

Proof. Choose a vertex $v$ of degree $\Delta(G)$. There are $\Delta(G)$ edges incident with $v$. Every pair of distinct edges among them shares the endpoint $v$, so a proper edge coloring must give all of them different colors. Thus any proper coloring uses at least $\Delta(G)$ colors, and minimizing over proper colorings gives $\chi'(G)\geq\Delta(G)$. $\square$

This argument supplies a necessary number of colors, not always a sufficient one. Another basic observation helps interpret the examples: each color class is a matching, because two edges of the same color cannot share an endpoint. Conversely, partitioning the edge set into matchings gives a proper edge coloring by assigning one color to each matching.

Proposition: A partition of $E(G)$ into $k$ matchings defines a proper edge coloring with $k$ colors.

Proof. Assign a different color to each of the $k$ matchings in the partition. Two edges that share an endpoint cannot belong to the same matching, by the definition of a matching. They therefore receive different colors. Every edge belongs to exactly one matching, so this assignment colors every edge properly. $\square$

These facts explain how to verify a coloring: check that every edge is assigned exactly once, and that each listed color class is a matching. To prove that the number of colors is minimal, pair the coloring with a lower bound, such as the maximum-degree bound.

Vizing’s Theorem

Theorem (Vizing): If $G$ is a finite simple graph with at least one edge, then $$ \chi'(G)\in\{\Delta(G),\Delta(G)+1\}. $$ Equivalently, every such graph has a proper edge coloring using at most $\Delta(G)+1$ colors. The proof of the upper bound is a standard result whose proof comes later in the course; it uses a recoloring argument. The lower bound is the proposition proved above.

The simplicity hypothesis matters: the theorem is stated here for graphs with no loops or multiple edges. Also, the theorem says that the answer is one of two values; it does not give a quick way to decide which value applies to an arbitrary graph. We will see a graph requiring the extra color and another that meets the lower bound exactly.

If $G$ is edgeless, then every vertex has degree zero and the empty assignment is a proper edge coloring using zero colors. Under our convention, $\chi'(G)=0$. This includes the graph with no vertices and any edgeless graph with isolated vertices. The separate convention is why the stated two-value form of the theorem assumes at least one edge.

Worked Examples of Both Outcomes

Worked Example: The Five-Cycle Requires an Extra Color

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. Each vertex is incident with two edges, so $\Delta(G)=2$. We will show that $\chi'(G)=3=\Delta(G)+1$.

First, two colors cannot suffice. A matching in this graph uses at most two edges: each edge in a matching uses two distinct vertices, and three disjoint edges would require six vertices, while $G$ has only five. In a proper coloring, each color class is a matching. Thus two colors could cover at most $2\cdot2=4$ edges, but $G$ has five edges. Therefore $\chi'(G)\geq3$.

Now assign red to $\{12,34\}$, blue to $\{23,45\}$, and green to $\{51\}$. Each of the three sets is a matching: in the red set the endpoints are $1,2,3,4$, all distinct; in the blue set they are $2,3,4,5$, all distinct; and the green set has just one edge. The sets are disjoint and together contain $2+2+1=5$ edges, exactly the five edges in $E$. They give a proper coloring with three colors.

Check: the lower bound gives $\chi'(G)\geq\Delta(G)=2$, while the matching count rules out two colors and the displayed coloring uses three. Hence $\chi'(G)=3=\Delta(G)+1$, as claimed.

Worked Example: The Complete Graph on Four Vertices Meets the Bound

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$, so $G=K_4$. Each vertex is adjacent to the other three vertices, giving $\Delta(G)=3$.

Use three colors with classes $\{12,34\}$, $\{13,24\}$, and $\{14,23\}$. In the first class the four endpoints are $1,2,3,4$, all distinct; in the second they are $1,3,2,4$, all distinct; and in the third they are $1,4,2,3$, all distinct. Each class is therefore a matching. The classes have no edge in common, and their six edges are precisely $12,13,14,23,24,34$, so they give a proper coloring using three colors.

The lower bound gives $\chi'(G)\geq\Delta(G)=3$, and the coloring gives $\chi'(G)\leq3$. Therefore $\chi'(G)=3=\Delta(G)$, and $K_4$ is class one.

Check: the graph has $3+3+3+3=12$ total degrees, which counts every edge twice, giving $12/2=6$ edges, in agreement with the listed edge set. Each of the three color classes contains two edges, for $2+2+2=6$ colored edges altogether.

Worked Example: A Star Uses One Color per Incident Edge

Let $G=(V,E)$ have $V=\{c,a,b,d\}$ and $E=\{ca,cb,cd\}$. The center $c$ has degree $3$, and each of $a,b,d$ has degree $1$, so $\Delta(G)=3$.

The three edges all meet at $c$, so they must receive pairwise distinct colors. This proves $\chi'(G)\geq3$. Assign red to $ca$, blue to $cb$, and green to $cd$. There is one edge in each color class, so each class is a matching; all three edges have been colored. Thus $\chi'(G)\leq3$, and $\chi'(G)=3=\Delta(G)$.

Check: the sum of the degrees is $3+1+1+1=6$, so the number of edges is $6/2=3$, matching the edge set. The coloring uses exactly three colors, one for each of those three edges.

Sharpness and a Common Mistake

The lower bound $\chi'(G)\geq\Delta(G)$ applies to every graph with an edge, but it does not determine whether the bound is attained. The five-cycle shows that one more color can be necessary, while $K_4$ and the star show that the maximum-degree bound can be exact. Since Vizing’s theorem guarantees that no finite simple graph with an edge needs more than one color beyond $\Delta(G)$, the five-cycle demonstrates that this upper bound is sharp: it cannot be reduced to $\Delta(G)$ for all such graphs.

Common mistake: It is incorrect to reason that because $\Delta(G)$ colors suffice at a vertex of maximum degree, they must suffice for the whole graph. That argument checks only the edges incident with one vertex. For the five-cycle, $\Delta(G)=2$, but assuming two colors suffice would allow at most two edges in each color class. Since each class is a matching on five vertices, it has at most two edges; the two classes together cover at most $2+2=4$ edges, fewer than the five required. The correction is to distinguish the local lower bound from a global coloring construction.

When applying Vizing’s theorem, first calculate $\Delta(G)$. Then construct a coloring if you want to prove $\chi'(G)=\Delta(G)$, or rule out a $\Delta(G)$-coloring and exhibit a $\Delta(G)+1$-coloring if you want to prove class two. The theorem guarantees that these are the only possibilities, but the exact classification requires evidence about the graph itself.

Check Your Understanding

For each question, justify the edge-coloring claim using the definitions, a coloring, or a lower bound.

Why must the edges incident with a vertex of degree $\Delta(G)$ receive $\Delta(G)$ distinct colors?
For the graph with $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$, give a proper edge coloring and determine $\chi'(G)$.
Explain why the edges of any one color in a proper edge coloring form a matching.
Why does the maximum-degree lower bound alone not prove that the five-cycle can be colored with two colors?
What is $\chi'(G)$ when $G$ has vertices but no edges, under the convention used here?