Four Checks for Edge-Coloring Arguments
Edge-coloring proofs often go wrong not because the main idea is unsuitable, but because a local condition is overlooked. A color must be checked at both endpoints of an edge; the maximum degree gives a lower bound, not always the answer; the bipartite hypothesis cannot be dropped; and a fan shift must preserve properness at every vertex it touches. We will test these points on small graphs, where every color assignment can be checked directly.
Throughout, graphs are finite and simple. An edge-coloring assigns a color to each edge. It is proper if any two edges sharing an endpoint receive different colors. The chromatic index \(\chi'(G)\) is the smallest number of colors in a proper edge-coloring of \(G\). A partial edge-coloring may leave some edges uncolored, but any two colored edges sharing an endpoint must still have different colors. When discussing a partial coloring, fix a palette \(C\); the missing-color set at a vertex \(v\) is \(M(v)=C\setminus\{\text{colors on colored edges incident with }v\}\).
Adjacent Edges Must Be Checked at Both Ends
This definition gives a practical test: for each color, list its edges and check that no vertex occurs twice. It is not enough that two edges have different other endpoints, or that a color appears only once at one end. If two edges meet at even one vertex, they cannot share a color.
Worked Example: Catching a Conflict at the Shared Vertex
Let \(G\) have \(V=\{1,2,3\}\) and \(E=\{12,23\}\). A proposed coloring assigns red to both edges. The edges have different other endpoints, but they both meet at vertex \(2\). Thus the red class \(\{12,23\}\) is not a matching, and the proposed coloring is not proper.
Correct the assignment by coloring \(12\) red and \(23\) blue. At vertex \(1\), only red occurs; at vertex \(2\), red and blue occur; at vertex \(3\), only blue occurs. No vertex is incident with two edges of the same color, so this is a proper coloring.
Check: The graph has two adjacent edges, so one color cannot suffice. The displayed coloring uses two colors. Therefore \(\chi'(G)=2\).
What the Maximum-Degree Bound Does—and Does Not—Say
Proof. If \(G\) has no edges, no colors are needed, and every vertex has degree \(0\), giving the stated equality. Otherwise, choose a vertex \(v\) of degree \(\Delta(G)\). In any proper edge-coloring, the \(\Delta(G)\) edges incident with \(v\) must all have different colors, since every pair of them shares \(v\). Hence at least \(\Delta(G)\) colors are required, so \(\chi'(G)\geq\Delta(G)\). \(\square\)
The inequality is a necessary condition on the number of colors. Treating it as the universal equality \(\chi'(G)=\Delta(G)\) is a common error. Vizing’s theorem gives a general upper bound for simple graphs, but it does not turn this lower bound into an equality in every graph.
Worked Example: Maximum Degree Is Not Always Enough
Let \(G=K_3\), with \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\). Each vertex is incident with two edges, so \(\Delta(G)=2\). The maximum-degree bound therefore says \(\chi'(G)\geq2\), not that two colors suffice.
To see why two colors fail, note that a color class must be a matching. In \(K_3\), any two distinct edges share a vertex, so a matching contains at most one edge. Two colors can therefore color at most two edges, but \(K_3\) has three edges. At least three colors are needed.
Assign red to \(12\), blue to \(23\), and green to \(13\). Each color class has one edge, so the coloring is proper and uses three colors. Thus \(\chi'(K_3)=3\).
Check: The lower bound gives \(2\), and the matching count proves that \(2\) colors cannot suffice. The displayed coloring gives an upper bound of \(3\); together these establish the exact value \(3\).
Do Not Drop the Bipartite Hypothesis
A theorem about bipartite graphs cannot be applied to an arbitrary graph merely because the graph has a convenient degree pattern. Kőnig’s line coloring theorem, covered in the earlier material on edge coloring, states that every finite bipartite graph \(G\) satisfies \(\chi'(G)=\Delta(G)\). Bipartite means that the vertices can be partitioned into two sets so that every edge joins different sets. The hypothesis is essential: the triangle in the previous example is not bipartite, and its chromatic index is greater than its maximum degree.
Worked Example: Applying the Bipartite Theorem Within Its Hypotheses
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), a 4-cycle. The partition \(\{1,3\}\), \(\{2,4\}\) shows that \(G\) is bipartite: each listed edge joins one part to the other. Every vertex has degree \(2\), so \(\Delta(G)=2\). Kőnig’s line coloring theorem applies and gives \(\chi'(G)=2\).
Here is the coloring explicitly: assign red to \(12\) and \(34\), and blue to \(23\) and \(41\). The red edges are disjoint, and the blue edges are disjoint, so the coloring is proper. It uses two colors, while the maximum-degree bound requires at least two.
Check: At vertices \(1,2,3,4\), the incident edge colors are respectively red and blue, red and blue, blue and red, and red and blue. Thus the assignment is proper, and the lower and upper bounds both equal \(2\).
Common error: “The graph has maximum degree \(2\), so it has a 2-edge-coloring.” The triangle disproves this statement. The valid conclusion in the bipartite case comes from Kőnig’s theorem, not from the degree calculation alone. First verify bipartiteness; then apply the theorem. If the graph is not bipartite, the maximum-degree lower bound still holds, but equality needs a separate argument.
Fan Shifts: Track the Edge and Its New Endpoint
A fan is used in Vizing’s recoloring method to move the uncolored edge through a sequence of edges incident with a common vertex. For this tutorial, the key issue is local: after moving colors, check the new color at the other endpoint of each moved edge, as well as at the common vertex. A color missing at one vertex is not automatically missing at another.
Proof. At \(x\), the recolored edges \(x y_0,\ldots,x y_{k-1}\) receive the distinct colors \(c_1,\ldots,c_k\). These are exactly the colors previously used on \(x y_1,\ldots,x y_k\), so no duplicate color is created at \(x\). At \(y_{i-1}\), the new color \(c_i\) was missing by hypothesis, so it conflicts with no already colored edge there. The edge \(x y_k\) is left uncolored, and no other edge changes; hence the partial coloring remains proper. Finally, if \(c\) is missing at \(x\) and \(y_k\), assigning \(c\) to \(x y_k\) creates no conflict at either endpoint. All the specified edges are then colored properly. \(\square\)
Worked Example: A Shift with Every Endpoint Checked
Use palette \(C=\{\text{red},\text{blue},\text{green}\}\). Let the graph have \(V=\{x,y_0,y_1,y_2,a,b,c\}\) and \(E=\{xy_0,y_0a,xy_1,y_1b,xy_2,y_2c\}\). In the partial coloring, leave \(xy_0\) uncolored; color \(y_0a\) blue, \(xy_1\) red, \(y_1b\) green, \(xy_2\) blue, and \(y_2c\) red.
At \(x\), the colored spokes have distinct colors red and blue, and green is missing. At \(y_0\), blue is used, so red is missing. At \(y_1\), red and green are used, so blue is missing. At \(y_2\), blue and red are used, so green is missing. Thus red is missing at \(y_0\), and blue is missing at \(y_1\): the sequence of spokes \(xy_0,xy_1,xy_2\) satisfies the consecutive shift conditions.
Shift the colors: move red from \(xy_1\) to \(xy_0\), then move blue from \(xy_2\) to \(xy_1\). The edge \(xy_2\) is now uncolored. At \(y_0\), the new red edge meets only the blue edge \(y_0a\). At \(y_1\), the new blue edge \(xy_1\) meets the green edge \(y_1b\). At \(x\), the moved spokes have different colors, red and blue. Since green is missing at both \(x\) and \(y_2\), color \(xy_2\) green.
Check: After completion, the colors at \(x\) are red on \(xy_0\), blue on \(xy_1\), and green on \(xy_2\). At \(y_0\), red differs from the blue on \(y_0a\); at \(y_1\), blue differs from the green on \(y_1b\); at \(y_2\), green differs from the red on \(y_2c\). The coloring is proper at every endpoint affected by the shift.
Common Fan-Recoloring Errors
Checking only the common vertex. Distinct colors on the spokes at \(x\) do not guarantee a proper partial coloring: a moved color may already occur on another edge at the spoke’s far endpoint. The proposition requires \(c_i\) to be missing at \(y_{i-1}\), and the example checks that condition before each shift.
Using the wrong color after a shift. In the example, after the shift \(xy_1\) is blue, not red: red moved to \(xy_0\). Saying that the new blue edge \(xy_1\) meets a red edge \(xy_1\) incorrectly assigns two colors to the same edge. The correct endpoint check is that \(xy_1\), now blue, meets the green edge \(y_1b\). Write down the edge-color assignment after every shift before checking conflicts.
Filling the final uncolored edge without two missing-color checks. The final color must be missing at both endpoints. A color absent at \(x\) may already occur on an edge at \(y_k\), and vice versa. In the worked example, green can finish the shift precisely because it is absent at both \(x\) and \(y_2\).
These checks are useful whenever a proof changes a coloring locally. Record which edges are colored, which color each receives, and which colors are missing at each affected vertex. Then verify properness at every endpoint. This procedure catches conflicts that a description of the idea alone can hide.
Check Your Understanding
For each question, distinguish what follows from a general edge-coloring rule from what requires a particular hypothesis.
- In a proper edge-coloring, why must the edges of one color form a matching?
- A graph has maximum degree \(3\). What lower bound follows for its chromatic index, and why does this not by itself prove equality?
- Give the vertex partition that certifies the 4-cycle in the worked example is bipartite. Which theorem then determines its chromatic index?
- In the fan example, list the colors missing at \(y_0,y_1,y_2\) before shifting.
- After the fan shift, why is green a valid color for \(xy_2\)? State the condition at each endpoint.