The Extension Problem
In an edge-coloring problem, a partial coloring may leave several edges uncolored. The extension step asks for more than a bound on the number of colors: given a particular uncolored edge, can the current coloring be changed so that this edge receives a color, without increasing the palette? In Vizing’s argument, a fan organizes the edges near one endpoint, while interchanging two colors along an alternating chain changes which colors are available.
Throughout, \(G=(V,E)\) is a finite simple graph with maximum degree \(\Delta=\Delta(G)\), and the palette \(C\) has exactly \(\Delta+1\) colors. A proper partial edge coloring assigns a color from \(C\) to some edges, with no two colored edges sharing a vertex receiving the same color. An edge not assigned a color is uncolored. For a vertex \(v\), let \(M(v)\) denote the set of colors in \(C\) not used on any colored edge incident with \(v\).
The condition on consecutive vertices says precisely that the color on \(xy_i\) can be moved onto \(xy_{i-1}\) without creating a conflict at \(y_{i-1}\). A color may be missing at more than one fan vertex; the definition only requires the indicated predecessor condition.
Proof. If \(j=1\), assign \(\gamma\) directly to \(xy_1\); it is missing at both endpoints. If \(j\ge2\), for each \(i=2,\ldots,j\), the color on \(xy_i\) is missing at \(y_{i-1}\). First move the color of \(xy_2\) to \(xy_1\), leaving \(xy_2\) uncolored. Then move the color of \(xy_3\) to \(xy_2\), and continue through \(i=j\). At each move the receiving vertex \(y_{i-1}\) is missing the moved color; at \(x\), that color was already used on \(xy_i\), and \(xy_i\) becomes uncolored in the same move. Thus no conflict is created at either endpoint. The result has \(xy_j\) uncolored. Now color \(xy_j\) with \(\gamma\), which is missing at \(x\) and \(y_j\). The root edge \(xy_1\) is colored, and all changes preserve properness. \(\square\)
It is useful to record why missing colors are available to work with. Since \(xy\) is uncolored, at most \(\deg(x)-1\) colored edges are incident with \(x\). Therefore \( |M(x)|\ge \Delta+1-(\deg(x)-1)\ge2\). The same calculation gives \( |M(y)|\ge2\). These lower bounds do not guarantee that \(M(x)\) and \(M(y)\) intersect; fans and color interchanges address that obstruction.
Two-Color Chains and the Fan-and-Chain Reduction
For distinct colors \(\alpha,\beta\), consider the subgraph made up of the edges colored \(\alpha\) or \(\beta\). At every vertex there is at most one incident edge of each color, so every vertex in this subgraph has degree at most two. Each of its connected components is therefore a path, a cycle, or an isolated vertex. Such a component is called an \(\alpha\beta\)-chain. Interchanging \(\alpha\) and \(\beta\) on all edges of one chain preserves properness: at an interior vertex of a path or cycle, the incident chain edges still have different colors, and at an endpoint the one chain edge merely changes color. Edges of other colors are untouched.
The key input from the earlier material on combining fans with two-color chains is the following precise reduction. Starting with a proper partial coloring and an uncolored root edge \(xy_1\), apply fan rotations and interchanges on two-color chains. Either these operations yield a proper partial coloring in which \(xy_1\) is colored, or they yield a proper partial coloring with \(xy_1\) still uncolored and a fan at \(x\), rooted at \(y_1\), with strictly more distinct fan vertices than before. This reduction is the role of the chain analysis: it makes progress either by completing the target edge or by enlarging the fan. Its proof uses the alternating-chain endpoint analysis from the earlier material; we use the stated reduction, not an assumption that any arbitrary switch will help.
Worked Example: Rotating a Fan to Use a Common Missing Color
Let \(V=\{x,a,b,c\}\) and \(E=\{xa,xb,xc\}\). This star has \(\Delta=3\), so use \(C=\{1,2,3,4\}\). Leave \(xa\) uncolored, color \(xb\) with \(1\), and color \(xc\) with \(2\). The coloring is proper: the two colored edges meet at \(x\) but have different colors. The list \(F=(a,b,c)\) is a fan because \(1\in M(a)\) and \(2\in M(b)\).
At \(x\), colors \(1\) and \(2\) are used, so \(M(x)=\{3,4\}\). At \(c\), only color \(2\) is used, so \(M(c)=\{1,3,4\}\). Choose \(\gamma=4\), which belongs to both sets. Rotate through \(j=3\): put color \(1\) on \(xa\), then put color \(2\) on \(xb\), leaving \(xc\) uncolored. Each move is allowed because \(1\) is missing at \(a\) and \(2\) is missing at \(b\). Finally put \(4\) on \(xc\).
Check: the resulting colors on \(xa,xb,xc\) are \(1,2,4\), respectively. They are distinct at \(x\), and each leaf has only one incident edge. The previously uncolored edge \(xa\) is now colored, and the number of colored edges has increased from \(2\) to \(3\).
Worked Example: Switching a Chain to Create a Common Missing Color
Let \(V=\{x,y,u,v,z,w\}\) and \(E=\{xy,xu,xv,yz,yw\}\). Here \(\Delta=3\), and take \(C=\{1,2,3,4\}\). Leave \(xy\) uncolored; color \(xu\) with \(2\), \(xv\) with \(3\), \(yz\) with \(1\), and \(yw\) with \(4\). This is proper, since the colors at \(x\) are \(2,3\) and those at \(y\) are \(1,4\).
The missing sets are \(M(x)=\{1,4\}\) and \(M(y)=\{2,3\}\), so there is no common missing color at the endpoints. Consider the \(1,2\)-chain containing \(x\). It consists only of \(xu\), because \(xu\) has color \(2\), and \(u\) has no other incident edge. Interchange \(1\) and \(2\) on this chain. The edge \(xu\) now has color \(1\), and \(x\) now has \(M(x)=\{2,4\}\). The edges at \(y\) have not changed, so \(M(y)=\{2,3\}\).
Now color \(xy\) with \(2\), which is missing at both endpoints. At \(x\), the colored incident edges have colors \(1,3,2\); at \(y\), they have colors \(1,4,2\). Each list has distinct colors, so the extension is proper.
Check: before the switch, the missing sets \(\{1,4\}\) and \(\{2,3\}\) were disjoint. After the switch they are \(\{2,4\}\) and \(\{2,3\}\), whose intersection is \(\{2\}\). The target edge receives exactly that common missing color.
The Fan-Extension Lemma
Proof. Begin with the given coloring and the one-vertex fan \(F=(y)\) rooted at \(y\). Apply the fan-and-chain reduction. If it colors \(xy\), the required modification is complete. Otherwise, it gives a proper partial coloring with the same uncolored root edge and a longer fan. Apply the reduction again whenever it does not complete the target edge.
Every fan consists of distinct neighbors of \(x\), so its length is at most \(\deg(x)\), which is at most \(\Delta\). Each unsuccessful application increases the integer length by at least one. Starting at length \(1\), there cannot be more than \(\Delta-1\) strict increases: after that many, the length is at least \(\Delta\), and no longer fan at \(x\) is possible. Consequently the reduction cannot keep enlarging the fan indefinitely. Its completion alternative must occur, and the resulting proper partial coloring assigns a color to \(xy\). No step introduces a color outside the palette \(C\). This proves the claim. \(\square\)
The conclusion concerns the chosen edge, not every uncolored edge at once. The coloring may still be partial after the extension. In particular, this lemma does not claim that one rotation alone will suffice: the chain interchanges may first be needed to alter which colors are missing.
Worked Example: Direct Extension Without a Fan Rotation
Let \(V=\{p,q,r,s\}\) and \(E=\{pq,pr,qs\}\). The graph has \(\Delta=2\), so use \(C=\{1,2,3\}\). Leave \(pq\) uncolored, color \(pr\) with \(1\), and color \(qs\) with \(2\). This is a proper partial coloring because the two colored edges are disjoint.
At \(p\), color \(1\) is used, so \(M(p)=\{2,3\}\). At \(q\), color \(2\) is used, so \(M(q)=\{1,3\}\). The common missing color is \(3\); assign it to \(pq\). The incident colors at \(p\) are now \(1,3\), and those at \(q\) are \(2,3\), so the coloring remains proper.
Check: the edge count changes from \(2\) colored edges to \(3\), and every edge in \(E\) now has a color. The color \(3\) was in the palette and missing at both endpoints, as required for a direct extension.
A Common Mistake
A fan rotation is valid only when the color being moved is missing at the vertex that receives it. For a concrete failure, let \(V=\{x,a,b,c\}\), \(E=\{xa,xb,ac\}\), \(\Delta=2\), and \(C=\{1,2,3\}\). Leave \(xa\) uncolored and color both \(xb\) and \(ac\) with \(1\). This partial coloring is proper: the two color-\(1\) edges do not share a vertex. But \(1\notin M(a)\), because \(ac\) already has color \(1\). The attempted calculation “move color \(1\) from \(xb\) onto \(xa\)” would give both \(xa\) and \(ac\) color \(1\), a conflict at \(a\). The correction is to verify the fan condition before each move: color \(1\) is not missing at \(a\), so \(b\) cannot be the next vertex after \(a\) in this fan. A valid extension argument must use an allowed fan rotation or a chain interchange that preserves properness.
The extension step matters because it turns a local partial coloring into measurable progress: one more edge becomes colored while the palette stays fixed. The proof depends on two distinct safeguards. Fan conditions justify each rotation at its receiving vertex, and two-color-chain interchanges preserve properness while changing missing colors. Confusing these roles—especially assuming that a color missing at one fan vertex is missing at every fan vertex—is a common source of invalid recoloring arguments.
Check Your Understanding
Use the definitions and extension argument to answer the following.
- In a fan \(F=(y_1,y_2,y_3)\), what condition must the color of \(xy_3\) satisfy for the rotation from \(xy_2\) to \(xy_3\) to be valid?
- Why does interchanging two colors on a single two-color chain preserve properness at its endpoints?
- Explain why the bound on fan length is \(\deg(x)\), even when the graph has vertices of degree smaller than \(\Delta\).
- In the chain-switch example, compute the missing sets at \(x\) and \(y\) after interchanging colors \(1\) and \(2\), and identify their intersection.
- Give a valid reason why the fan-extension lemma does not imply that one recoloring step colors every uncolored edge in the graph.