Two Colors in a Partial Edge Coloring
In Vizing’s proof, one works with a proper edge coloring that may leave some edges uncolored. A useful local operation is to exchange two colors along a maximal alternating path. The operation is simple, but its safety depends on using the whole path: a swap along only part of it can make two incident edges receive the same color. We will identify exactly which vertices are affected and how their missing colors change.
Let \(G=(V,E)\) be a finite simple graph, let \(C\) be a finite set of colors, and let \(E_0\subseteq E\) be the set of colored edges. A partial proper edge coloring is a function \(\varphi:E_0\to C\) such that any two colored edges incident with the same vertex have different colors. An edge outside \(E_0\) is uncolored. The missing-color set at a vertex \(v\) is
Thus \(c\in M_\varphi(v)\) means that no colored edge incident with \(v\) has color \(c\). This is a statement about the colored edges only; uncolored edges do not remove colors from \(M_\varphi(v)\).
The definition includes all vertices, even vertices incident with no edge of color \(a\) or \(b\). Such a vertex is an isolated component, not a nontrivial chain. A cycle component is also possible; it has no endpoints. The distinction matters because the endpoint missing-color statement applies to path components, not to cycles.
Why the Components Are Paths or Cycles
Proof. At any vertex, at most one incident edge has color \(a\) and at most one has color \(b\), by properness. Therefore the degree in the two-color subgraph is at most \(2\). Consider a connected component with at least one edge. If it has a vertex of degree \(1\), start there and follow edges, at each step continuing along the only available edge other than the one just used, if such an edge exists. No vertex can have three incident edges in this component, so there is no branch. Because the graph is finite, this process ends; it gives a path. No vertex of the component can lie outside this path, since connectivity would require an additional edge into the path, either creating a branch or extending an endpoint where the process had already stopped. If instead every vertex in the component has degree \(2\), following edges must eventually return to a previously visited vertex. The degree bound and connectedness then make the component a cycle. At any vertex of degree \(2\), one incident edge has color \(a\) and the other has color \(b\). Hence colors alternate around a cycle. Returning to the starting vertex after alternation requires an even number of edges. Components with no edges are isolated vertices. \(\square\)
In particular, a nontrivial path component has two endpoints, each incident with exactly one edge in the two-color subgraph. At such an endpoint, exactly one of \(a,b\) is missing: the other color is used by the path’s incident edge, and maximality ensures that no further incident edge has either color. Every internal vertex of the path has one incident edge of each color.
The Color-Swap Theorem
Proof. Define \(\varphi'\) by replacing color \(a\) with \(b\) and color \(b\) with \(a\) on the edges of \(P\), and by setting \(\varphi'(e)=\varphi(e)\) on every other colored edge. We first check properness at each vertex. A vertex internal to \(P\) has one incident edge of color \(a\) and one of color \(b\); after the swap it still has one of each. At an endpoint, the unique incident edge of \(P\) changes from one of these colors to the other. No other incident edge has either color, since the endpoint is an endpoint of a whole component of the two-color subgraph. Thus the changed edge cannot conflict there with an unchanged edge. All other incident colored edges have colors outside \(\{a,b\}\), and the swap introduces neither of those colors onto such an edge. Vertices not on \(P\) have no changed incident edges. Therefore \(\varphi'\) is proper.
At an internal vertex of \(P\), both \(a\) and \(b\) are used before and after the swap, and all other incident colors are unchanged. Its missing-color set is unchanged. At an endpoint, exactly one of \(a,b\) is missing before the swap, and the path edge uses the other. After the edge changes color, these two roles reverse: the color previously used by that edge becomes missing, and the previously missing color is used. Colors outside \(\{a,b\}\) are unchanged at every vertex. This proves the stated missing-color changes. \(\square\)
The conclusion is local and exact. A swap does not change the missing-color sets at internal vertices, and it does not alter any color other than \(a\) or \(b\). At the two endpoints, it transfers which of these two colors is available. If the two-color component is an isolated vertex, both colors are missing there and there are no edges to swap. If it is a cycle, each vertex has both colors before and after a swap around the whole cycle, so no endpoint change occurs.
Worked Example: A Chain Whose Endpoints Miss the Same Color
Let \(G\) have vertex set \(V=\{u,v,w,x\}\) and edge set \(E=\{uv,vw,wx\}\). Let the palette be \(C=\{a,b,c\}\), and color \(uv\) with \(a\), \(vw\) with \(b\), and \(wx\) with \(a\). This is a proper coloring: at \(v\) the incident colors are \(a,b\), and at \(w\) they are \(b,a\). The whole graph is the two-color chain \(u,v,w,x\).
Before the swap, \(u\) and \(x\) each have one incident edge of color \(a\), so \(M_\varphi(u)=M_\varphi(x)=\{b,c\}\). At \(v\) and \(w\), both \(a\) and \(b\) occur, so \(M_\varphi(v)=M_\varphi(w)=\{c\}\). Swap \(a\) and \(b\) on all three edges. The new colors are \(\varphi'(uv)=b\), \(\varphi'(vw)=a\), and \(\varphi'(wx)=b\). Thus \(M_{\varphi'}(u)=M_{\varphi'}(x)=\{a,c\}\), while \(M_{\varphi'}(v)=M_{\varphi'}(w)=\{c\}\).
Check: at \(v\), the new incident colors are \(b\) and \(a\); at \(w\), they are \(a\) and \(b\). The coloring remains proper, and the endpoints now miss \(a\) rather than \(b\), as the theorem predicts.
Worked Example: A Chain Whose Endpoints Miss Opposite Colors
Let \(G\) have \(V=\{p,q,r\}\), \(E=\{pq,qr\}\), and palette \(C=\{a,b,c\}\). Color \(pq\) with \(a\) and \(qr\) with \(b\). The two edges form a maximal two-color chain, with endpoints \(p,r\) and internal vertex \(q\).
At \(p\), color \(a\) is used, so \(M_\varphi(p)=\{b,c\}\). At \(r\), color \(b\) is used, so \(M_\varphi(r)=\{a,c\}\). At \(q\), both colors are used, so \(M_\varphi(q)=\{c\}\). After swapping the two chain edges, \(pq\) has color \(b\) and \(qr\) has color \(a\). The new missing sets are \(M_{\varphi'}(p)=\{a,c\}\), \(M_{\varphi'}(r)=\{b,c\}\), and \(M_{\varphi'}(q)=\{c\}\).
Check: the two edges at \(q\) still have different colors, \(b\) and \(a\). At \(p\), the formerly missing \(b\) is now used and \(a\) is missing; at \(r\), the reverse happens. In both endpoint sets, \(c\) remains missing because it is neither used nor changed.
Why Maximality Is Essential
The theorem depends on swapping an entire path component. A segment of an alternating path may stop at a vertex where another edge of one of the two colors remains. Swapping only the segment can then place the same color on both incident edges at that vertex.
Worked Example: A Nonmaximal Swap Creates a Conflict
Let \(G\) have \(V=\{p,q,r,s\}\), \(E=\{pq,qr,rs\}\), and palette \(C=\{a,b,c\}\). Color \(pq\) with \(a\), \(qr\) with \(b\), and \(rs\) with \(a\). The full path \(p,q,r,s\) is a maximal two-color chain. Consider instead swapping only the nonmaximal segment \(p,q,r\). This changes \(pq\) to \(b\) and \(qr\) to \(a\), but leaves \(rs\) colored \(a\).
Now both \(qr\) and \(rs\) have color \(a\), and both are incident with \(r\). The result is not proper. To correct the operation, swap on the full chain: the colors become \(b,a,b\) on \(pq,qr,rs\), respectively. At \(q\) the incident colors are \(b,a\), and at \(r\) they are \(a,b\), so the full swap is proper. Before this full swap, \(p\) and \(s\) each miss \(\{b,c\}\), while \(q\) and \(r\) each miss \(\{c\}\). Afterwards, \(p\) and \(s\) each miss \(\{a,c\}\), and \(q,r\) still each miss \(\{c\}\).
Check: the failure of the short swap is at \(r\), exactly where the omitted edge \(rs\) continues the two-color component. Swapping the entire component changes that edge too, removing the conflict.
How Two-Color Chains Are Used
In a partial edge coloring, knowing that a color is missing at a vertex is useful because an incident uncolored edge may be assigned that color without conflicting with any colored edge at that vertex. A two-color swap can change which of two colors is missing at the endpoints while preserving the coloring everywhere else. This is the local mechanism used in Vizing’s argument: it allows color availability to be moved between vertices while keeping all colored edges proper.
The theorem alone does not say that an arbitrary uncolored edge can now be colored, nor that a swap can be combined with any other recoloring without further checks. Its guarantee is precise: properness is preserved on the full maximal chain, internal missing-color sets stay fixed, and the endpoint memberships of the two selected colors are exchanged. When chains interact with a fan, the order and compatibility of operations require additional argument.
Common pitfall. “The colors alternate” is not enough to justify a swap on any chosen alternating segment. One must also know that the segment has no omitted continuation at either endpoint. The third example shows the concrete failure: the short segment is alternating, but its swap creates two incident \(a\)-edges. Maximality rules out exactly this endpoint conflict.
Check Your Understanding
For each question, track only the colored edges when determining missing-color sets.
- Why can a vertex have at most two incident edges in a two-color subgraph of a proper partial edge coloring?
- If a chain begins with color \(a\) and ends with color \(b\), which of \(a,b\) is missing at each endpoint before the swap? What happens afterwards?
- Why does a swap on a whole path component preserve properness at its internal vertices?
- What are the missing-color sets at the vertices of an isolated component of the two-color subgraph, with respect to the two selected colors?
- In the nonmaximal-swap example, identify the vertex where properness fails and the unchanged edge responsible for the conflict.