A -edge colouring of a graph is a function such that incident edges receive different colours.
Given a graph , the edge chromatic number or chromatic index is the least for which is -edge-colourable.
Suppose we have a colouring of all but one edge using colours . Then we wish to recolour so all the edges are coloured.
Note that one colour is unused (``missing'') at every vertex.
Let be the uncoloured edge. We construct a sequence of edges and a sequence of colours as follows.
Pick to be a colour missing at . Let be an edge with colour . We stop with when either is a colour unused at , or is already used on for .
If was a colour unused at then we recolour with for . This finishes the easy case where we can recolour the edges touching to give a a colouring for .
Otherwise we recolour with for and uncolour . Notice that (red) is missing at both and . Let blue be a colour unused at .
If none of the above hold, then we consider the subgraph of red and blue edges. The components of this subgraph are paths or cycles. The vertices are the end vertices of paths. Therefore they cannot all belong to the same component.
Select a component that contains exactly one of these vertices. Now swap over red and blue in this component. Now one of the conditions above must apply.
If is bipartite, then .
Now we prove the theorem for -regular bipartite multi-graphs by induction on .
Clearly true for .
Let be an edge of , Delete the vertices and . Because and were in different vertex classes, it is possible to add fewer than new edges to make a new -regular bipartite multi-graph . Now we colour by the induction hypothesis. Certainly not all the colours were used to colour the new edges. Let red be one of these colours. Certainly the red edges in with form a -factor in . Deleting this -factor gives a -regular bipartite multigraph .
Now colour by the induction hypothesis, then add the -factor back, to obtain a colouring of .
Let finite subsets of , so that each vertex has a ``paint box'' . We say that is -choosable if such that and is a vertex colouring.
We say that is -choosable if is -choosable whenever , .
Clearly if is -choosable it is -choosable. However it is not necessarily true that if is -choosable it is -colourable.
The list chromatic number of a graph is the least such that is -choosable.
John Fremlin 2010-02-17