A Complete Proof of Vizing’s Theorem

The Extension Problem

An edge-coloring assigns colors to edges so that edges sharing a vertex receive different colors. The chromatic index \(\chi'(G)\) is the minimum number of colors in a proper edge-coloring of \(G\). Vizing’s theorem gives a universal upper bound: a finite simple graph of maximum degree \(\Delta(G)\) can be edge-colored with at most \(\Delta(G)+1\) colors. The proof is an extension argument. Remove one edge, color the rest, and then use a fan and a two-color chain to put a color on the uncolored edge without creating a conflict.

We will work with a palette \(C\) of \(D+1\) colors, where \(D\) is an integer and every vertex has degree at most \(D\). A partial edge-coloring is a proper coloring of only some of the edges. For a vertex \(v\), let \(M(v)\) be the set of colors in \(C\) that do not occur on any colored edge incident with \(v\). Since at most \(D\) colored edges can meet \(v\), while \(|C|=D+1\), at least one color is missing at every vertex.

Definition: Suppose \(xy_1\) is the only uncolored edge. A fan with center \(x\) is a sequence of distinct neighbors \(y_1,y_2,\ldots,y_k\) such that, for each \(i>1\), the color on \(xy_i\) is missing at some earlier fan vertex \(y_j\), where \(j<i\). A fan is maximal if no new neighbor of \(x\) can be appended while preserving this property.

To construct a maximal fan, start with \(y_1\), then repeatedly append a neighbor \(z\) not already in the sequence whenever the color on \(xz\) is missing at a fan vertex. The edge \(xz\) is colored because \(xy_1\) is the only uncolored edge. The graph is finite, so this process terminates. For each \(i>1\), choose and record one earlier index \(p(i)<i\) such that the color on \(xy_i\) is missing at \(y_{p(i)}\). We call \(p(i)\) the parent index of \(i\).

Shifting a Fan

The parent indices make it possible to move the uncolored edge from \(xy_1\) to any chosen fan edge. Starting at an index \(i\), repeatedly follow parent indices backwards. The indices strictly decrease, so this process reaches \(1\). Reversing the sequence gives indices \(1=i_0<i_1<\cdots<i_r=i\) with \(p(i_\ell)=i_{\ell-1}\) for each \(\ell>0\).

Fan-shift rule: For this parent chain, give \(xy_{i_{\ell-1}}\) the former color of \(xy_{i_\ell}\), for \(\ell=1,\ldots,r\), and leave \(xy_i\) uncolored. If a color \(\gamma\) is missing at both \(x\) and \(y_i\), then coloring the newly uncolored edge \(xy_i\) with \(\gamma\) completes the partial coloring.

Justification. The former color of \(xy_{i_\ell}\) is missing at \(y_{i_{\ell-1}}\) by the parent condition, so the reassignment causes no conflict at that endpoint. At \(x\), the colors on the fan edges were distinct because the original partial coloring was proper. The shift moves these colors one edge along the chain: all the old colors remain present at \(x\), except the former color on \(xy_i\), and no color is duplicated there. Thus the shift is proper and leaves \(xy_i\) as the only uncolored edge. A color \(\gamma\) missing at \(x\) remains missing there: the shift uses only colors that were already present at \(x\). It is also still missing at \(y_i\), since the shift only removes the color on \(xy_i\) and does not change any other edge incident with \(y_i\). Therefore coloring \(xy_i\) with \(\gamma\) is valid. \(\square\)

Worked Example: Shifting to a Fan Edge

Let \(V=\{x,y_1,y_2,a,b,c\}\) and \(E=\{xy_1,xy_2,y_1a,y_1b,y_2c\}\). Use the palette \(C=\{1,2,3,4\}\). Leave \(xy_1\) uncolored, and color \(xy_2\) with \(1\), \(y_1a\) with \(2\), \(y_1b\) with \(3\), and \(y_2c\) with \(3\). This is proper: at \(x\) the only colored edge has color \(1\); at \(y_1\) the colors are \(2,3\); and at \(y_2\) they are \(1,3\).

The fan \(y_1,y_2\) is valid because the color \(1\) on \(xy_2\) is missing at \(y_1\). The color \(2\) is missing at \(x\) and at \(y_2\). Shift along the parent chain \(1,2\): give \(xy_1\) the former color \(1\) of \(xy_2\), leaving \(xy_2\) uncolored. Then color \(xy_2\) with \(2\). The completed coloring has colors \(1,2\) on \(xy_1,xy_2\), respectively, and the other edges retain their colors \(2,3,3\) as listed.

Check: At \(x\), the incident edge colors are now \(1,2\); at \(y_1\), they are \(1,2,3\); and at \(y_2\), they are \(2,3\). Each set has distinct colors, so the extension is proper.

The Fan-and-Chain Extension Lemma

Lemma: Let \(G\) be a finite simple graph with maximum degree at most \(D\), and let \(C\) be a palette of \(D+1\) colors. If all but one edge of \(G\) have been properly colored from \(C\), the coloring can be extended to the remaining edge.

Proof. Write the uncolored edge as \(xy_1\), and construct a maximal fan \(y_1,\ldots,y_k\) centered at \(x\). If some color \(\gamma\) belongs to \(M(x)\cap M(y_i)\) for a fan vertex \(y_i\), apply the fan-shift rule and color the resulting uncolored edge with \(\gamma\). This includes the case \(i=1\), when the uncolored edge can be colored directly. We may therefore assume that \(M(x)\cap M(y_i)=\varnothing\) for every \(i\).

Choose a color \(\alpha\in M(x)\) and a fan vertex \(y_k\). Since \(M(y_k)\) is nonempty, choose \(\beta\in M(y_k)\). The assumption of no common missing color gives \(\alpha\notin M(y_k)\) and \(\beta\notin M(x)\). Consider the subgraph consisting only of edges colored \(\alpha\) or \(\beta\), and take its connected component containing \(y_k\). At every vertex there is at most one incident edge of each of these colors, so every vertex has degree at most two in this subgraph. The vertex \(y_k\) has degree one in it: \(\beta\) is missing there and \(\alpha\) is present. The vertex \(x\) also has degree one: \(\alpha\) is missing there and \(\beta\) is present.

If this component does not contain \(x\), interchange \(\alpha\) and \(\beta\) on every edge of the component. This operation preserves properness: at each vertex of the component, the incident edges of these two colors are exchanged, and all other edge colors are unchanged. Since \(\beta\) was missing at \(y_k\) and \(\alpha\) was present there, after the interchange \(\alpha\) is missing at \(y_k\). The color \(\alpha\) is still missing at \(x\), since the component does not contain \(x\). We now have a common missing color and can use the fan-shift rule.

It remains to consider the case where the component contains \(x\). A connected subgraph of maximum degree two that contains a degree-one vertex is a path, not a cycle. Its endpoints here are \(y_k\) and \(x\), so the path ends at \(x\) on a \(\beta\)-colored edge \(xz\). If \(z\) were not already a fan vertex, we could append it to the fan: the color \(\beta\) on \(xz\) is missing at \(y_k\). This would contradict maximality. Thus \(z=y_i\) for some \(i>1\); it cannot be \(y_1\), whose edge to \(x\) is uncolored. By the fan condition, the color \(\beta\) on \(xy_i\) is missing at some earlier \(y_j\), with \(j<i\). In particular, \(j<k\), so \(y_j\) is neither endpoint \(y_k\) nor \(x\) of the path. Because \(\beta\) is missing at \(y_j\), that vertex cannot lie internally on the path either: every internal vertex of the path is incident with one \(\beta\)-edge. Hence \(y_j\) is outside the component.

Now interchange \(\alpha\) and \(\beta\) on the whole path. At \(x\), the incident \(\beta\)-edge becomes an \(\alpha\)-edge, so \(\beta\) becomes missing there. The interchange does not affect \(y_j\), where \(\beta\) was already missing. Thus \(\beta\) is missing at both \(x\) and \(y_j\). Apply the fan-shift rule to \(y_j\) and color the resulting uncolored edge with \(\beta\). In every case the original partial coloring extends, proving the lemma. \(\square\)

Worked Chain Cases

Worked Example: A Two-Color Chain Avoids the Center

Let \(V=\{x,y_1,y_2,z,a,b,p,q,r\}\), with edge set \(E=\{xy_1,xy_2,xz,y_1a,y_1b,y_2p,y_2r,pq\}\). Use \(C=\{1,2,3,4\}\). Leave \(xy_1\) uncolored; color \(xy_2=3\), \(xz=2\), \(y_1a=1\), \(y_1b=4\), \(y_2p=1\), \(y_2r=4\), and \(pq=2\). Each vertex has distinct colors on its colored incident edges.

Here \(M(x)=\{1,4\}\), \(M(y_1)=\{2,3\}\), and \(M(y_2)=\{2\}\), so there is no common missing color at either fan vertex. The fan \(y_1,y_2\) is valid because \(3\), the color on \(xy_2\), is missing at \(y_1\). Choose \(\alpha=1\) and \(\beta=2\). The \(\alpha,\beta\)-component from \(y_2\) is the path \(y_2,p,q\), with edge colors \(1,2\); it does not contain \(x\). Swap the colors on both path edges. Now \(y_2p=2\), \(pq=1\), and \(1\) is missing at both \(x\) and \(y_2\).

Shift the fan: give \(xy_1\) color \(3\), leaving \(xy_2\) uncolored, then color \(xy_2\) with \(1\). At \(x\), the resulting colors on \(xy_1,xy_2,xz\) are \(3,1,2\). At \(y_1\), the colors are \(3,1,4\); at \(y_2\), they are \(1,2,4\). All are distinct, verifying the completed coloring.

Worked Example: A Two-Color Chain Reaches the Center

Let \(V=\{x,y_1,y_2,y_3,a,b,c,d,p,q\}\) and \(E=\{xy_1,xy_2,xy_3,y_1p,y_1q,y_2b,y_2d,y_3a,y_3c,ab\}\). Use \(C=\{1,2,3,4\}\). Leave \(xy_1\) uncolored and color \(xy_2=2\), \(xy_3=3\), \(y_1p=1\), \(y_1q=4\), \(y_2b=1\), \(y_2d=4\), \(y_3a=1\), \(y_3c=4\), and \(ab=2\). At each vertex the colored incident edges have distinct colors.

We have \(M(x)=\{1,4\}\), \(M(y_1)=\{2,3\}\), \(M(y_2)=\{3\}\), and \(M(y_3)=\{2\}\). The sequence \(y_1,y_2,y_3\) is a fan: the color \(2\) on \(xy_2\) is missing at \(y_1\), and the color \(3\) on \(xy_3\) is missing at \(y_2\). Choose \(\alpha=1\), \(\beta=2\), and start the two-color path at \(y_3\). It is \(y_3,a,b,y_2,x\), with successive edge colors \(1,2,1,2\). It reaches \(x\) on the edge \(xy_2\).

Swap \(1\) and \(2\) on the entire path. The changed edges are \(y_3a=2\), \(ab=1\), \(by_2=2\), and \(xy_2=1\). Now \(2\) is missing at \(x\); it is also missing at \(y_1\), which lies outside the path. Color the uncolored edge \(xy_1\) with \(2\). At \(x\), the colors on \(xy_1,xy_2,xy_3\) are \(2,1,3\); at \(y_1\), the colors on \(xy_1,y_1p,y_1q\) are \(2,1,4\). The extension is proper.

Vizing’s Theorem

Theorem (Vizing): Every finite simple graph \(G\) with at least one edge has an edge-coloring with at most \(\Delta(G)+1\) colors. An edgeless graph requires no colors.

Proof. Put \(D=\Delta(G)\), and use the palette \(C\) of \(D+1\) colors. We prove by induction on the number \(m=|E(G)|\) that every finite simple graph of maximum degree at most \(D\) can be edge-colored from this palette. If \(m=0\), there are no edges to color, so the claim holds. Now let \(m>0\), choose an edge \(e\), and form \(H=G-e\). This graph has \(m-1\) edges and maximum degree at most \(D\). By the induction hypothesis, \(H\) has a proper edge-coloring from \(C\). Regard it as a partial coloring of \(G\) with \(e\) uncolored. The extension lemma applies and colors \(e\) while preserving properness. Thus the claim holds for \(m\), completing the induction. Taking \(D=\Delta(G)\) gives the stated bound. \(\square\)

Why the Whole Chain Must Be Swapped

A two-color change must be made on the entire connected component of the two-color subgraph, not just on a convenient part of its alternating path. For example, in the preceding chain-avoids-center example, the path \(y_2,p,q\) has colors \(1,2\). If only \(y_2p\) is changed from \(1\) to \(2\), while \(pq\) is left colored \(2\), then \(p\) has two incident edges of color \(2\). That is not a proper coloring. Swapping both path edges instead gives colors \(2,1\), leaving distinct colors at \(p\) and exchanging which of \(1,2\) is missing at the endpoint \(y_2\).

The proof uses two complementary operations. Fan shifts move the uncolored edge while maintaining properness at the center; two-color swaps change which colors are missing at selected vertices. Maximality of the fan matters only when the alternating path reaches the center: its final neighbor must already be in the fan, which supplies an earlier vertex where the needed color is missing. Together these steps turn any coloring with one uncolored edge into a complete coloring, and induction applies this extension repeatedly.

Check Your Understanding

Use the fan-shift rule and extension argument to answer the following.

Why is at least one color missing at every vertex when the palette has \(D+1\) colors and the maximum degree is at most \(D\)?
In a fan with parent indices \(p(2)=1\), \(p(3)=1\), and \(p(4)=3\), write the parent chain from \(1\) to \(4\).
Why can the \(\alpha,\beta\)-component containing \(y_k\) not be a cycle in the chain argument?
In the chain-avoids-center example, recompute the missing-color sets at \(x,y_1,y_2\) after the swap and before the fan shift.
In the chain-reaches-center example, identify the earlier fan vertex at which \(\beta\) is missing, and explain why it is not on the alternating path.