Alternating Paths for Bipartite Edge Recoloring

Two Colors Isolate a Recoloring Route

In an edge coloring, changing one edge at a time can create a conflict: two edges meeting at a vertex might end up with the same color. Alternating paths give a controlled alternative. If the edges of a path alternate between two colors, exchanging those colors along the path keeps every internal vertex properly colored. The endpoints may change which of the two colors is available, which is the useful effect in many recoloring arguments.

All graphs in this tutorial are finite and simple. A proper edge coloring assigns colors to some or all edges so that any two colored edges sharing a vertex have different colors. A coloring may be partial: some edges may be uncolored. A color \(c\) is missing at a vertex \(v\) if no colored edge incident with \(v\) has color \(c\). An alternating path for two distinct colors \(a,b\) is a path whose consecutive edges alternate between \(a\) and \(b\).

We focus on bipartite graphs: a graph is bipartite if its vertices can be partitioned into two sets so that every edge joins one set to the other. Bipartiteness provides a useful parity rule: along any path the vertices alternate between the two sets. The local recoloring operation itself works in any graph; the bipartite setting makes the path parity especially informative.

The Shape of a Two-Color Component

Proof. At any vertex, at most one incident edge can have color \(a\) and at most one can have color \(b\), because the coloring is proper. Thus every vertex of the two-color subgraph has degree at most \(2\). If a vertex has degree \(2\), its two incident edges have different colors, again by properness. Therefore colors alternate whenever we continue through a vertex of degree \(2\).

Now consider a connected component containing at least one edge. If it has a vertex of degree \(1\), start there and follow the only edge; at each subsequent vertex there is at most one unused edge to continue along. No vertex can be revisited: a revisit would close a cycle, and a vertex on that cycle would then have its two cycle edges, leaving no way for the original degree-\(1\) start to connect to it without giving some vertex degree at least \(3\). Finiteness therefore makes this traversal end at another degree-\(1\) vertex, and connectedness means it has covered the component. The component is a path. If there is no degree-\(1\) vertex, every vertex has degree \(2\). Following edges must eventually revisit a vertex, forming a cycle; each vertex on the cycle already has degree \(2\), so connectedness leaves no other vertices or edges in the component. It is a cycle. In both cases, the colors alternate at every degree-\(2\) vertex. \(\square\)

In a bipartite graph, every cycle has even length because each step changes sides and returning to the starting side requires an even number of steps. An alternating cycle also has even length: its edge colors alternate, and the last edge must have a different color from the first at their shared vertex. For an alternating path, the first and last edge colors are the same exactly when the path has odd length.

Exchanging the Colors

Proof. We check every vertex that could be affected. At a vertex of \(H\) incident with two edges of \(H\), one has color \(a\) and the other has color \(b\). After the exchange, they still have different colors. At a vertex incident with exactly one edge of \(H\), that edge changes from one of \(a,b\) to the other. There cannot be another incident edge of either color outside \(H\): any such edge would belong to the two-color subgraph and be connected to \(H\), hence would itself be in the same component. All other incident colored edges have colors different from both \(a\) and \(b\), so the changed edge conflicts with none of them. Vertices not incident with \(H\) are unchanged. Thus no pair of incident colored edges receives the same color, and the new coloring is proper. \(\square\)

The exchange preserves the total number of edges in \(H\), but it swaps the counts of the two colors there. It does not generally preserve the individual counts. On an alternating cycle, or an even-length alternating path, the counts are equal, so swapping leaves each individual count unchanged. On an odd-length path, one color occurs once more than the other, and the exchange reverses which color has the larger count.

In a bipartite graph, a path with an even number of edges has its endpoints in the same part, while a path with an odd number of edges has its endpoints in opposite parts. This follows by changing parts once for every edge traversed. The endpoint rule and the parity rule can therefore be used together when a recoloring argument needs to coordinate the colors available at two vertices.

Using an Exchange to Change Endpoint Availability

A recoloring is often useful because it changes what can be done at an endpoint, rather than because it changes the number of edges of each color. In a partial coloring, an uncolored edge can be colored \(c\) if \(c\) is missing at both endpoints. An alternating-path exchange can change which of the two colors is missing at the path endpoints while leaving the internal vertices properly colored.

Common Pitfall: Confusing Total and Individual Counts

A frequent error is to say that exchanging two colors on an alternating component “preserves the number of edges of each color.” It preserves the number of edges in the component, not necessarily the count of each color separately. In the odd-length path example, the incorrect calculation would leave the counts at red \(2\), blue \(1\). But the actual new edge colors are blue, red, blue, so the correct counts are red \(1\), blue \(2\). Individual counts stay equal only when they were equal before the exchange.

Another mistake is to exchange colors on an arbitrary collection of edges and assume properness follows. The component condition matters: at every internal vertex of an alternating component, there is one edge of each color, and swapping them retains that pattern. If one recolors only part of a route without checking its endpoints and internal vertices, a conflict may result. For a reliable argument, identify the two-color component, verify the alternating sequence, and then check the endpoints separately from the internal vertices.

These exchanges are a local tool, not a complete edge-coloring algorithm by themselves. They do not assert that every partial coloring can be extended, nor do they determine the minimum number of colors required. Their precise guarantee is that swapping the two colors on a full two-color component preserves properness and reverses the two-color availability at its path endpoints.