From a Partial Coloring to a Completed Edge
Vizing’s fan procedure changes a partial edge coloring in a controlled way. It does not recolor edges arbitrarily: a fan organizes the edges around one vertex, a shift moves the uncolored edge along that fan, and sometimes a two-color swap makes a useful color available at the new endpoint. The important bookkeeping is local. At every step, record which colors are missing and check that no two edges incident to a vertex receive the same color.
Throughout, \(G=(V,E)\) is a finite simple graph, and the available colors are \(1,\ldots,k\). A partial proper edge coloring is a coloring of some of the edges such that any two colored edges sharing a vertex have different colors. Uncolored edges have no color. For a vertex \(v\), write \(M(v)\) for the set of available colors not used on any colored edge incident to \(v\). In particular, an uncolored edge does not use a color. A color can be assigned to an uncolored edge \(uv\) precisely when it belongs to \(M(u)\cap M(v)\).
To extend the coloring, first inspect \(M(x)\) and the missing-color sets of the fan vertices. If a color is missing at \(x\) and at some \(y_j\), shift the fan only as far as \(y_j\), then color the newly uncolored edge. If there is no such common color, a two-color component can sometimes create one: choose a color missing at \(x\) and one missing at \(y_j\), then interchange those colors along the component containing \(y_j\), provided that component does not contain \(x\).
Why Shifts and Swaps Preserve Properness
Proof. Before the shift, the colored edges \(xy_2,\ldots,xy_j\) have distinct colors, because they all meet at \(x\). Each color moved onto \(xy_i\) is missing at \(y_i\), by the fan condition. Thus the new edge color does not conflict at \(y_i\). At \(x\), the shift merely moves the distinct colors from \(xy_2,\ldots,xy_j\) onto \(xy_1,\ldots,xy_{j-1}\); no duplicate color is introduced, and \(xy_j\) becomes uncolored. All other edges are unchanged, so the coloring remains proper. Since \(\gamma\) is missing at \(x\) and \(y_j\), assigning \(\gamma\) to \(xy_j\) preserves properness at both endpoints. \(\square\)
Proof. At every vertex there is at most one incident edge of color \(\alpha\) and at most one of color \(\beta\), by properness. Interchanging the two colors therefore leaves at most one incident edge of either color at that vertex. Other colors are unchanged, so properness is preserved. At \(y\), no incident edge had color \(\beta\). If an incident edge had color \(\alpha\), it is changed to \(\beta\); if none did, none is introduced. Hence \(\alpha\) is missing at \(y\) after the swap. \(\square\)
The subgraph made from two colors has degree at most two at each vertex. Its connected components are paths, cycles, or isolated vertices. The swap must be made on the component containing the chosen fan vertex, not on every edge of either color. If that component contains \(x\), the swap may change which color is missing at \(x\), so the useful missing-color pair is not preserved.
Worked Examples
Worked Example: Shift a Fan to a Common Missing Color
Let \(V=\{x,a,b,c\}\) and \(E=\{xa,xb,xc\}\). Use colors \(1,2,3\), with \(xa\) uncolored, \(xb\) colored \(1\), and \(xc\) colored \(2\). The coloring is proper because the two colored edges at \(x\) have different colors.
The missing sets, obtained by checking the colored incident edges, are \(M(x)=\{3\}\), \(M(a)=\{1,2,3\}\), \(M(b)=\{2,3\}\), and \(M(c)=\{1,3\}\). The sequence \(F=(a,b,c)\) is a fan: \(xb\) has color \(1\), missing at \(a\), and \(xc\) has color \(2\), missing at \(b\). Color \(3\) is missing at both \(x\) and \(c\).
Shift to \(c\). Move color \(1\) from \(xb\) to \(xa\), leaving \(xb\) temporarily uncolored. Then move color \(2\) from \(xc\) to \(xb\), leaving \(xc\) uncolored. The intermediate colored edges at \(x\) are now \(xa=1\) and \(xb=2\); at \(b\), color \(2\) was missing before the shift. Finally assign color \(3\) to \(xc\). The completed coloring is \(xa=1\), \(xb=2\), \(xc=3\).
Check: The three edges incident to \(x\) now have the distinct colors \(1,2,3\). Each of \(a,b,c\) has just one incident edge, so no conflict occurs there.
Worked Example: Swap a Two-Color Component, Then Shift
Let \(V=\{x,a,b,c,d,e\}\) and \(E=\{xa,xb,xc,cd,de\}\). Use colors \(1,2,3\), with \(xa\) uncolored and colored edges \(xb=1\), \(xc=2\), \(cd=3\), and \(de=1\). These colored edges form a proper partial coloring: at \(x\) the used colors are \(1,2\); at \(c\) they are \(2,3\); at \(d\) they are \(3,1\); and the other vertices have at most one colored incident edge.
Checking those incident colors gives \(M(x)=\{3\}\), \(M(a)=\{1,2,3\}\), \(M(b)=\{2,3\}\), and \(M(c)=\{1\}\). The sequence \(F=(a,b,c)\) is a fan because color \(1\) on \(xb\) is missing at \(a\), and color \(2\) on \(xc\) is missing at \(b\). No color is missing at both \(x\) and \(c\): the only color missing at \(x\) is \(3\), while \(M(c)=\{1\}\).
Take \(\alpha=3\), missing at \(x\), and \(\beta=1\), missing at \(c\). The component containing \(c\) in the subgraph of colors \(1\) and \(3\) is the path \(c,d,e\), whose edges are \(cd=3\) and \(de=1\). The edge \(xb=1\) is in a different component, so this path does not contain \(x\). Swap \(1\) and \(3\) on \(c,d,e\): now \(cd=1\) and \(de=3\). At \(c\), the incident colored edges have colors \(2\) and \(1\), so \(3\) is missing; at \(x\), the incident colored edges still have colors \(1\) and \(2\), so \(3\) is still missing.
Now shift the fan to \(c\): recolor \(xa\) with \(1\), recolor \(xb\) with \(2\), and leave \(xc\) uncolored. Assign \(3\) to \(xc\). The final edge colors are \(xa=1\), \(xb=2\), \(xc=3\), \(cd=1\), and \(de=3\).
Check: At \(x\), the incident colors are \(1,2,3\); at \(c\), they are \(3,1\); and at \(d\), they are \(1,3\). Each set has no repeated color. The swap and shift therefore give a proper coloring of every edge in \(E\).
Worked Example: Stop the Shift at the Correct Fan Vertex
Let \(V=\{x,a,b,c,d\}\) and \(E=\{xa,xb,xc,cd\}\). Use colors \(1,2,3\), with \(xa\) uncolored and \(xb=1\), \(xc=2\), \(cd=3\). The colored edges are proper: at \(x\) the colors are \(1,2\), and at \(c\) they are \(2,3\).
Checking incident colors gives \(M(x)=\{3\}\), \(M(a)=\{1,2,3\}\), \(M(b)=\{2,3\}\), and \(M(c)=\{1\}\). The fan \(F=(a,b,c)\) satisfies its conditions: color \(1\) on \(xb\) is missing at \(a\), and color \(2\) on \(xc\) is missing at \(b\). The common missing color \(3\) occurs at \(x\) and \(b\), so the target is \(y_2=b\), not \(y_3=c\).
Shift only the prefix before \(b\): put color \(1\) on \(xa\), leave \(xb\) uncolored, and then put color \(3\) on \(xb\). The edge \(xc\) remains color \(2\), and \(cd\) remains color \(3\). Thus the final colors are \(xa=1\), \(xb=3\), \(xc=2\), and \(cd=3\).
Check: At \(x\), the incident colors are \(1,3,2\), all distinct. At \(c\), the incident colors are \(2,3\), also distinct. In particular, shifting all the way to \(c\) and then assigning \(3\) to \(xc\) would be wrong: \(cd\) already has color \(3\). The correct shift stops at the vertex where the common missing color was found.
The Local Extension Rule and Its Limits
Proof. In the first case, apply the fan-shift lemma with the shared missing color. For the second case, before the swap \(\beta\) is missing at \(y_j\) and \(\alpha\) is missing at \(x\). The two-color swap lemma shows that after swapping on the component containing \(y_j\), color \(\alpha\) is missing at \(y_j\). Since \(x\) is outside that component, none of its incident edges changes, so \(\alpha\) remains missing at \(x\). The fan-shift lemma, now with common missing color \(\alpha\), completes the edge. \(\square\)
This proposition describes two common successful branches of the procedure; it is not a claim that every chosen fan vertex and color pair works. When a two-color component contains \(x\), or a selected target has no usable common missing color after the swap, that branch cannot be used as stated. The full fan-extension argument, developed in the proof of Vizing’s theorem, handles the remaining choices by adjusting the fan and the choice of colors. In an application, do not silently assume that a swap leaves the center’s missing set unchanged: first check whether the swapped component contains \(x\).
Common Pitfalls
Shifting too far. A fan is a sequence of potential targets, not an instruction to move the uncolored edge to its final listed vertex. In the third example, color \(3\) is missing at \(x\) and \(b\), but not at \(c\), because \(cd\) already has color \(3\). A full shift followed by coloring \(xc\) with \(3\) would create a conflict at \(c\). Shift only to the vertex where the common missing color is available.
Swapping colors globally. A two-color swap applies to one connected component of the subgraph formed by those colors. In the second example, the \(1,3\)-component containing \(c\) is \(c,d,e\); the separate edge \(xb\) is not recolored. Swapping all edges of colors \(1\) and \(3\) would change the color missing at \(x\), defeating the purpose of the step.
Forgetting the fan condition. To shift a color from \(xy_{i+1}\) onto \(xy_i\), that color must be missing at \(y_i\). The fan definition guarantees this for each step. Without that condition, the shift may create a repeated color at the receiving vertex even if the colors around \(x\) remain distinct.
Check Your Understanding
For each question, keep track of the partial coloring before and after every recoloring step.
- In a fan \(F=(y_1,y_2,y_3,y_4)\), what edges change when shifting to \(y_3\), and which edge is uncolored afterward?
- Why does a two-color swap on the component containing \(y\) make \(\alpha\) missing at \(y\) when \(\beta\) was missing there?
- In the second worked example, why does swapping colors on the component containing \(c\) leave color \(3\) missing at \(x\)?
- Give a reason that assigning a color missing at \(x\) but not at the other endpoint of an uncolored edge may fail.
- What must be checked before using a two-color swap to preserve a color missing at the fan center?