Motivation
At a vertex of maximum degree, every incident edge needs a different color. This gives a lower bound for edge coloring, but choosing colors greedily can become stuck even when every vertex has an unused color. The available colors at the two ends of the next edge may differ.
A fan moves the location of the uncolored edge while preserving properness. A two-color path changes which colors are available. Their combination needs care: a path interchange can destroy one of the fan's conditions. The proof below identifies exactly that condition and shows which fan prefix remains usable.
The argument extends the bipartite result to every simple graph, with a constructive upper bound, examples attaining it and an explicit elementary implementation. It does not decide whether the smaller maximum-degree palette suffices for a given graph, and it does not extend the simple-graph conclusion to arbitrary parallel edges.
For a comparison proof, see Misra and Gries’s constructive presentation. The exposition here makes the changing fan relation and the elementary implementation bounds explicit.
Definitions
Definition 10.3.1
(Partial edge coloring and missing colors)
Let be a finite simple undirected graph on vertices, with maximum degree . A proper partial edge coloring assigns colors to some edges so that distinct colored edges incident at one vertex have different colors. Other edges remain uncolored. A color is missing at a vertex if none of its currently colored incident edges uses it.
Use a fixed palette of colors. Every vertex has at least one missing color, even after all its edges are colored. At a vertex incident with an uncolored edge there are at least two, although the proof only needs a chosen missing color.
Fix an uncolored edge . A sequential fan at center is a list of distinct neighbors such that each edge for is colored and its color is missing at . A prefix is again a fan. The graph is simple, so a fan neighbor specifies one unique center edge.
A maximal sequential fan cannot be extended by a new neighbor whose center edge is colored with a color missing at the current last vertex. Maximal refers to extension of this particular list, not to the largest possible number of fan vertices among all lists.
For two distinct colors , the subgraph consisting of their colored edges has degree at most two at every vertex. Its components are alternating paths, even alternating cycles and isolated vertices. Interchanging and on one whole component preserves proper partial edge coloring.
Theorem/Proposition
Theorem 10.3.2
(A fan transports an uncolored edge without creating a conflict)
Suppose is a fan, and color is missing at both and . Move the color of onto for from one through , removing it from as the blank advances. Then color the final blank with .
The resulting partial coloring is proper and has exactly one more colored edge. Only the selected center edges have changed; no other uncolored edge is affected.
Theorem 10.3.3
(One two-color path always creates a usable fan prefix)
For every uncolored edge and a maximal sequential fan, choose missing at its center and missing at its last vertex. Either is already missing at the center, or interchanging on the component containing the center produces a fan prefix whose last vertex and center both miss .
The choice of prefix depends on whether one particular predecessor lies on the path. Rotating the old fan indiscriminately after the interchange is not part of the theorem.
Theorem 10.3.4
(The maximum-degree lower bound needs at most one extra color)
Every finite simple graph satisfies
where is its least proper edge-color count. The edgeless graph has both and zero. Repeated fan/path insertion constructs the upper-bound coloring.
With indexed adjacency lists and a vertex-by-color incidence table, a direct implementation uses time and storage, where is the edge count. These are elementary word-operation bounds, not an optimized edge-coloring runtime or a minimum-palette decision algorithm.
Proof sketch or proof idea
Move the blank along a fan
Proof
(Fan rotation)
Initially is blank. The color on is missing at , so remove it from and put it on . At that color merely moves between two incident edges; it is never duplicated. At it was missing, and removing it at cannot create a conflict.
Continue forward. The color about to move was missing at its receiving fan vertex in the original coloring. Earlier blank moves have not introduced that color there: each earlier receiver is a different vertex, and the present receiver has only had its own center edge cleared. Thus every move remains proper. Equivalently, the final rotation assigns each receiver its successor's old color and removes the final center edge's color.
At the set of colors present is unchanged by the rotation. At the last fan vertex the only changed incident edge is cleared. Therefore a color initially missing at both remains missing there after rotation. Putting it on the final blank increases the colored-edge count by one, proving the first theorem. A one-vertex fan simply colors the original edge directly.
Grow a fan until every possible next center edge is accounted for
Proof
(Growing a maximal fan)
Start with the list containing only . Whenever a colored edge from reaches a neighbor outside the list and its color is missing at the current last vertex, append that neighbor. Every appended vertex is new, so the process stops after at most the degree of many vertices. The resulting list is maximal in the stated extension sense.
Choose missing at and missing at the last vertex . If is also missing at , the entire fan is immediately usable and no path interchange is needed. Otherwise and are distinct. There is a unique -colored edge incident at because the partial coloring is proper.
Maximality implies that this -edge is one of the colored fan edges: if its neighbor were outside the fan, that neighbor could be appended, since is missing at . Write it as , with , and put . The fan condition says is missing at . Notice that is different from the last vertex.
Interchange from the center and track the sole endangered condition
Proof
(Path interchange and its two cases)
Let be the component containing . At there is a -edge and no -edge, so has degree one in that component. A finite connected graph of maximum degree two with such an endpoint is a simple path, not a cycle. Its first edge has color . Interchange the two colors along . The result is proper, and is now missing at .
Before the interchange, no fan edge had color because was missing at . Only had color . Every other fan-edge color is therefore outside the pair . Its edge color and its missing status at the predecessor remain unchanged by the interchange. The only fan relation that might need repair is the one involving and predecessor .
There are two cases.
If is not on , it still misses . The prefix ending at excludes , so all its fan relations are among the unchanged ones. This prefix is usable with missing at both its last vertex and its center . Rotate that prefix and finish.
If lies on , then before interchange it misses . Such a vertex cannot be internal on a nontrivial path, since an internal vertex has one edge of each color. It is therefore the endpoint other than . Its incident path edge has color , and interchange makes missing there. At the same time the center edge changes from to , so its color is now missing at . The formerly endangered fan relation is restored.
The last vertex was missing before interchange. If it belonged to , it too would be an endpoint. But the two endpoints are and , both different from . Thus the last vertex is outside and still misses . All fan relations now hold, so the whole fan is usable. Rotate it and color its final blank .
Proof X-ray
One exceptional relation determines the prefix choice
Simplicity, maximality and properness are each used at one point. Maximality places the unique -edge at inside the fan, as some with ; without it that edge could lead to a vertex outside the list. Properness with missing at makes an endpoint of its component, so is a path, and it ensures that no fan edge has color and only has color . The interchange can therefore break exactly one fan relation, the one between and .
The case split is on whether lies on . If not, the prefix ending at never uses . If so, misses , so it cannot be internal and must be the other endpoint; the interchange turns into color and frees at , which repairs the relation. Endpoint counting closes this second case: has only the endpoints and , so , which also misses , lies off the path and still misses . Simplicity makes each fan vertex name a single center edge; with parallel edges the bound itself fails, as the counterexample below shows.
This completes every case without assuming that a path interchange preserves an arbitrary fan. Each insertion maintains properness and adds one colored edge. Starting from no colored edges and repeating finitely many times colors the entire graph with the fixed palette. A maximum-degree vertex requires distinct colors on its incident edges, proving the lower bound. The edgeless case uses no colors and needs no insertion.
Account for a direct implementation
Proof
(Cost of a direct implementation)
Store, for each vertex and each palette color, either its unique incident edge of that color or an absent marker. Store edge endpoints, colors and adjacency lists as well. The table has entries and permits constant-time missing-color tests and next-edge queries for an alternating path.
To extend a fan, scan the at most center neighbors and test whether the edge is colored, its neighbor is outside the fan, and its color is missing at the current end. At most extensions or a final failed scan give work. Finding the two missing colors costs linear palette scans.
The alternating path contains at most vertices. Retain its edge list and membership marks, clear the relevant old table entries, then install the interchanged colors and their entries. Clearing first avoids mistaking a temporary table collision for a final coloring conflict. This takes linear path work. Inspect the membership of , select the prefix and move the blank along at most fan edges, updating table entries.
Thus one insertion costs and initialization costs . There are insertions. The stored table, lists, path and fan give the claimed storage bound.
Worked examples
Worked example 10.3.5
(A triangle already needs the extra color)
A triangle has maximum degree two. Any two of its three edges share a vertex, so all three require different colors. Its edge chromatic number is three, exactly one above its maximum degree.
After two edges have been colored differently, the endpoints of the third may miss different colors from a smaller two-color palette. The theorem uses three colors throughout, making the recoloring guarantee possible. Vertex coloring and edge coloring are separate problems even when this small graph happens to need three for both.
Worked example 10.3.6
(A fan can be rotated without any two-color switch)
Let the center be and take edges blank, color one and color two. Suppose color one is missing at , color two at , and color three at both and . The list is a fan.
Move one to and clear ; move two to and clear ; color with three. The incident colors at are now one,two,three, and the receiving endpoints had the required missing colors. Other incident edges at the fan vertices can be present, provided those missing-color conditions hold.
Worked example 10.3.7
(Odd complete graphs give an infinite tight family)
For the complete graph on vertices with , maximum degree is and the number of edges is . One color class is a matching and contains at most edges. Covering all edges therefore needs at least colors.
The proved upper bound supplies that many, so its edge chromatic number is exactly . In contrast, the complete graph on four vertices has a three-color edge coloring by the matchings ; ; and . There the maximum-degree palette of three already suffices.
Concept lensAlgorithmic
A local recoloring operation preserves progress while changing its route
The number of colored edges is the global progress measure. Fan rotations move a blank, and alternating paths exchange availability without changing that number. The final shared missing color adds one edge. The invariant guarantees that this progress survives even when the originally chosen full fan must be shortened.
Common mistakes
Counterexample mode
Parallel edges invalidate the simple-graph bound
Put two parallel edges on each side of a three-vertex triangle. The maximum degree is four, but any two of its six edges share an endpoint. Every color class has at most one edge, so six colors are required, exceeding five. The general simple-graph conclusion does not apply to this multigraph.
Common mistake
(Interchanging only part of a component)
Do not interchange just an initial portion of a two-color component unless its endpoint conditions are proved; switching a whole component is what preserves properness. On a path with colored and colored , switching only gives two edges of color .
Common mistake
(Rotating the whole fan after an interchange)
Do not rotate the pre-interchange full fan without checking its exceptional relation. When is not on , the edge now has color , and nothing guarantees that is missing at . Rotating through would move onto and may duplicate it at ; only the prefix ending at is safe.
Common mistake
(One spare color is not a classification)
A construction with one spare color does not by itself identify the graphs that can dispense with it. The algorithm uses colors on and on alike, yet needs only three colors and needs five.
Summary
A sequential fan transports an uncolored center edge. Maximality locates a last missing color on a fan edge, and one alternating-path interchange leaves either a usable prefix or the entire repaired fan. Repeated insertions prove the maximum-degree-plus-one bound with explicit elementary work, while odd complete graphs and parallel-edge counterexamples show its sharpness and scope.
Exercises
Quick check
(Explain why a maximal fan containing only its initial vertex always lets the edge be colored directly with some missing color at that vertex.)
If the chosen missing color were present at the center, inspect its neighbor.
Solution · Answer
Choose missing at the lone fan vertex. If were present at , its unique incident edge could not be the blank edge. Its other endpoint would be a new fan neighbor with missing at the old last vertex, contradicting maximality. Thus is missing at as well and directly colors the blank. The argument uses the simple graph's unique edge to that original neighbor.
Quick check
(In the path-interchange proof, why can the predecessor and the last fan vertex not both lie on the center’s alternating path before the interchange?)
Both miss , while the center already occupies one endpoint.
Solution · Answer
Before interchange the center misses but has , making it one endpoint of a nontrivial path. Any other vertex on that path which misses must be its other endpoint; an internal vertex has both colors. The predecessor and the last vertex are distinct, so they cannot both occupy that one endpoint.
Quick check
(Determine the edge chromatic numbers of a five-cycle and a five-vertex complete graph. Give lower bounds that match the theorem's upper bound.)
A color class is a matching; for the cycle also consider parity.
Solution · Answer
The five-cycle has degree two and cannot be edge-colored with two colors: walking around the cycle would force alternating colors and then give the same color to the first and last incident edges at the starting vertex. Three suffice by the theorem. The five-vertex complete graph has ten edges, and every matching has at most two, so it needs at least five colors. Its maximum degree is four, and the theorem gives five, attaining that lower bound.