Motivation
Vertex coloring separates adjacent vertices. Edge coloring instead separates tasks sharing an endpoint: incident edges must receive different colors. Every high-degree vertex immediately gives a lower bound, but it is not obvious whether that local demand is the only obstruction.
For bipartite graphs it is. One proof completes the graph to a regular bipartite multigraph and repeatedly removes perfect matchings. A second proof inserts edges one at a time and repairs a conflict by swapping two colors along a path. The latter explains exactly where bipartiteness prevents the repair from disturbing the other endpoint.
The first proof uses the previously proved bipartite Hall theorem; the second gives a separate direct construction. General edge-coloring theorems outside the bipartite hypothesis are not imported without proof.
Definitions
Definition 10.2.1
(Proper edge colors and maximum degree)
Let be a finite undirected bipartite multigraph with specified sides . Each edge has one endpoint on each side. Parallel labeled edges are allowed; loops are not. Degrees count parallel edges separately. Write for maximum degree, taking when there are no edges.
A proper edge coloring assigns a color to each edge so edges sharing a vertex have different colors. Its minimum palette size is the edge-chromatic number , with value zero for an edgeless graph. Each individual color class is a matching. This problem differs from assigning colors to the vertices.
In a partial proper coloring using palette , a color is missing at a vertex if no currently colored incident edge has that color. Fix two different colors . The subgraph containing only their colored edges has degree at most two; its components are paths, even alternating cycles, or isolated vertices. A component incident to a vertex missing one of the colors cannot be a cycle.
A regular completion may add dummy vertices and parallel edges. Those additions serve a proof; after decomposing the larger graph into matchings, restrict each color class back to the original labeled edges.
Theorem/Proposition
Theorem 10.2.2
(Bipartite edge coloring attains the degree bound)
For every finite bipartite multigraph,
Equivalently its edges partition into matchings, with empty classes allowed when describing a fixed palette. The statement includes parallel edges and disconnected components.
Theorem 10.2.3
(Regular bipartite multigraphs split into perfect matchings)
A finite -regular bipartite multigraph with has sides of equal size and has a perfect matching. Repeated removal decomposes it into edge-disjoint perfect matchings.
Every finite bipartite multigraph of maximum degree can be enlarged to a -regular one with equally sized sides by adding vertices and edges. Restricting its decomposition proves the edge-coloring theorem.
Theorem 10.2.4
(A two-color path repair gives a direct algorithm)
Suppose all but one edge , with , are already properly colored from the -color palette. Choose a missing color at and a missing color at . If they differ, the component of the two-color subgraph containing does not contain . Swapping the two colors on that component makes missing at both endpoints, so can be colored .
Using incidence-by-color tables, sequential insertion of all edges on vertices takes elementary operations and storage. This is a simple constructive bound, not a fastest edge-coloring implementation.
Proof sketch or proof idea
Proof
(The degree lower bound)
Every set of incident edges needs distinct colors, so . For zero maximum degree there are no edges and the assertion follows from the empty coloring. We now give two full proofs of the matching upper bound.
Regularity turns Hall's condition into degree counting
Proof
(Regular decomposition and completion)
In a -regular bipartite multigraph, counting all edges by their left and right endpoints gives , so the sides have equal size. For any subset of the left side, exactly edges leave it, and all end in its neighbor set. At most edges can enter that set in total. Thus .
The proved Hall theorem gives a matching saturating the left side and hence both equal-sized sides. Parallel edges do not affect the neighbor criterion: a matching in the associated simple bipartite graph can choose one available original edge for each of its pairs. Removing the perfect matching reduces every degree by one. Apply the argument repeatedly until the graph is edgeless, proving the regular decomposition.
For a general graph, add isolated vertices until both sides have size . Each vertex has a deficit equal to minus its degree. The sum of deficits on either side is , so both totals agree.
If this total is positive, choose a vertex of positive deficit on each side and join them by an added edge, allowing a parallel edge when necessary. Both deficits decrease by one. Repeating terminates after exactly the deficit total number of additions. All degrees become . Decompose the completed graph and keep only original edges in each matching. This supplies a proper original edge coloring with the required palette.
This existence proof does not assume that regular completion remains simple. Forcing simplicity during the additions would impose an unnecessary restriction and could invalidate that elementary construction. Parallel labels are harmless for both degree counting and the final restriction.
Why a two-color repair avoids the other endpoint
Proof
(Alternating-path repair)
For the direct proof, process original edges in any order. Before inserting , each endpoint has at most colored incident edges, so it has a missing palette color. If a color is missing at both, use it immediately. Otherwise select distinct as in the theorem.
At there is no edge, so its two-color component is a path beginning at or an isolated vertex. If belonged to that path, the path would begin with a edge and end with an edge, since lacks . Alternation would make its number of edges even. But a bipartite path of even length has endpoints on the same side, whereas lie on opposite sides. This contradiction shows that is not in the component.
Swap and throughout the component. At an internal vertex, the two incident component colors simply exchange; endpoints still have at most one of each. No edge of either color crosses from the component to its complement by the component definition, and all other colors stay unchanged. Properness is preserved everywhere.
Because was missing at , the new missing color there is . Vertex is unaffected and still misses . Assign it to the new edge. This extends the proper partial coloring, so induction over all edges proves the theorem constructively, including multigraphs. A parallel pair can form a two-edge alternating cycle elsewhere, but the component at the deficient endpoint is still a path and the parity argument remains valid.
Proof X-ray
Where bipartiteness and the degree bound enter the repair
The repair proof uses three facts, each at one point. The degree bound supplies the missing colors: before is inserted, each endpoint has at most colored edges, so some palette color is free at and some at . Properness and the choice of fix the shape of the component: has no edge and at most one edge, so the component at is a path starting at , never a cycle. Bipartiteness enters only in the parity step. If the path reached , it would start with at and end with at ; alternation forces an even number of edges, and an even path joins two vertices on the same side, while and .
The swap is safe because the component is a whole component: no or edge leaves it, so exchanging the two colors cannot create a clash with an edge outside it. The induction then closes edge by edge, and the palette never grows. In a triangle the parity step is exactly the one that fails: the path from one endpoint can end at the other.
Implementing the repair without searching every incident edge repeatedly
Proof
(Cost of the table implementation)
Store, for every vertex and palette color, the ID of its incident edge of that color or an empty marker. A proper coloring makes this entry unambiguous even with parallel edges. Initializing the tables takes work. Scanning its palette finds a missing color at either endpoint in .
To find the component from , follow the alternating color through table lookups. It is a path with at most edges, because a maximum-degree-two component starting at an endpoint cannot revisit a vertex. Record those edges, clear their old incidence entries, and then assign their exchanged colors and write the new entries. Clearing first avoids overwriting a table entry still needed during the update. The component search and update use work and temporary path storage.
Each edge insertion consequently costs after initialization. Store the graph and color labels in edge entries and the incidence tables in entries. The stated bound counts ordinary array accesses and finite integer indices; it does not hide a search for arbitrary external labels in a constant-time operation.
The direct algorithm does not need to materialize the potentially larger regular completion. The two proofs establish the same existence theorem through different useful invariants: one removes a perfect matching from every regular degree layer, while the other preserves properness through a local alternating repair.
Worked examples
Worked example 10.2.5
(A complete two-by-three graph needs three edge colors)
For , each left vertex has degree three and each right vertex degree two. Color the three edges of the first left vertex with one, two and three in right-vertex order. Color those of the second with two, three and one.
Each row uses distinct colors, and each right vertex sees two distinct colors, so this is proper and attains . The regular-completion proof adds one dummy left vertex, joining it to all three right vertices to obtain a three-regular graph. Its perfect-matching colors restrict to exactly such a valid three-color pattern.
Worked example 10.2.6
(One alternating path frees the desired color)
Let the sides be and . The already colored edges are of color two, of color one, of color two and of color one. Insert the uncolored edge . The final graph has maximum degree two.
Color one is missing at and color two at . The two-color component at is the path , which excludes . Swap its colors to one, two and one. Now color two is missing at both , so give it to . All degree-two vertices see one of each color, and the original edge labels and endpoints are unchanged.
Worked example 10.2.7
(Parallel edges show why edge and vertex colors differ)
Take two vertices on opposite sides and join them by three parallel labeled edges. Their maximum degree is three, and all three edges share both endpoints, so three different edge colors are necessary and sufficient.
The underlying vertex-coloring problem needs only two colors. Parallel edges do not add new vertex-adjacency requirements, but they do add distinct incident edges competing for edge colors. Neither theorem's parameter can be substituted for the other's simply because the same graph is being drawn.
Concept lensCombinatorial
An edge color is one matching layer
A palette partitions the edge set into groups that never reuse an endpoint. Regularity makes each layer cover every vertex; irregular graphs leave some vertices idle in individual layers. The degree lower bound records the greatest number of local demands, and bipartiteness is what lets these demands be coordinated into exactly that many matching layers.
Common mistakes
Counterexample mode
An odd cycle needs more than its maximum degree
A triangle has maximum degree two but needs three edge colors: each of its three edges meets both others. More generally an odd cycle cannot alternate two colors consistently around its closure. Three suffice by alternating one and two along all but its final edge and giving the final edge color three. Thus its edge-chromatic number is three, while its maximum degree is two.
Common mistake
(Swapping on a path that reaches the other endpoint)
Do not apply the two-color endpoint argument without opposite bipartition sides. In the triangle with colored one and colored two, insert with palette . Color two is missing at and color one at , but the component at is the path , which reaches . Swapping gives color two and color one, so now misses one and misses two: the conflict has only moved.
Common mistake
(A color class need not be a perfect matching)
In an irregular graph a color class is a matching, not necessarily a perfect matching. A path with two edges has ; each of its two color classes is a single edge and misses one of the three vertices. Only the layers of the regular completion are perfect matchings.
Common mistake
(Reporting the dummy edges)
Dummy edges used in regular completion must be removed before reporting the coloring of the original graph. For the completion adds a left vertex joined to all three right vertices, and each of the three perfect matchings uses one of these added edges. The reported coloring is the restriction to the six original edges.
Summary
Maximum degree is the exact edge-color requirement for finite bipartite multigraphs. Hall's theorem proves a regular perfect-matching decomposition, while two-color path swaps give a direct incremental algorithm. Bipartite parity prevents the repair conflict; odd cycles demonstrate why the hypothesis and the distinction from vertex coloring matter.
Exercises
Quick check
(Give an explicit three-edge-coloring of , using a rule based on its row and column indices.)
Use indices zero, one and two and work modulo three.
Solution · Answer
Label each side by indices zero, one and two. Give edge color . Along a fixed row, the three column values give every color once; along a fixed column, the three row values do the same. Hence incident edges always differ. The degree-three lower bound proves optimality.
Quick check
(For a star with leaves, determine its edge-chromatic number and its vertex-chromatic number. Explain the difference when is large.)
All edges meet at the center, but no two leaves are adjacent.
Solution · Answer
The star has maximum degree , so it needs edge colors, one for each edge at its center. It needs exactly two vertex colors: one for the center and another for all leaves. Since at least one edge exists, one vertex color is impossible. For large the edge palette grows while the vertex palette remains two, illustrating the distinct constraints directly.
Quick check
(Explain why a two-color alternating component beginning at a vertex missing one color cannot be a cycle, including the possibility of parallel edges.)
Inspect its component degree at the starting vertex before using any parity argument.
Solution · Answer
Properness permits at most one incident edge of either chosen color. Missing one therefore leaves degree zero or one in that subgraph. A connected component containing such a vertex is isolated or a path, since all its vertices have degree at most two. It cannot be a cycle, whose vertices all have component degree two. A parallel two-edge cycle also gives degree two at both endpoints, so it cannot contain the deficient vertex. The subsequent bipartite parity argument applies to the resulting path.