Vizing's Theorem haiku

Induction on n.
Swap available colours
and find SDR.

Vizing's theorem says:

For any simple graph GG, the edge chromatic number χ(G)χ'(G) is at most Δ(G)+1Δ(G) + 1.

The proofShort proofs of classical theorems. Journal of Graph Theory 44(3). J Adrian Bondy (2003). is by induction on the number of vertices; pick a vertex vv and start with a (Δ(G)+1)(Δ(G)+1)-edge-colouring of GvG-v.

Ideally, we could just colour the edges around vv and extend the edge-colouring to one of GG. Those colours would need to be a system of distinct representatives (SDR) for the sets of colours still available at each of the neighbours of vv.

If we can't find a full SDR, then we can still try to colour as many of vv's edges as possible. Then, if an edge uvuv is still uncoloured, we can follow a proof of Hall's Theorem to get a set of coloured edges u1v,u2v,,ukvu_1 v, u_2 v, \ldots, u_k v such that:

Note also that

The first and third facts put together tell us that some colour (say, blue) is available at two vertices among uu and u1,u2,uku_1, u_2, \ldots u_k.

The second fact implies that any colour (e.g. red) still available at vv can't be available at any of the uiu_i, as otherwise we could swap around the colours to colour uvuv and then use red for uivu_i v.

Look at the subgraph HH of GG formed by the red and blue edges — it's made of paths and even cycles. We know that vv is incident with a blue edge but not a red one, so it's the end of a path in HH.

We also know that there are two vertices among u,u1,u2,uku, u_1, u_2, \ldots u_k that are incident with a red edge but not a blue one; those are also ends of paths in HH. The paths might be the same as each other, and one might be the same as vv's path, but the important thing is that we have a red-blue path where at least one of the ends is a neighbour uu' of vv and the other end is any vertex other than vv.

We can now modify the colouring of GvG-v to swap red and blue along this path, which frees up red at uu'. If uu' is uu itself, then we can colour uvuv red; otherwise, we can uncolour uvu'v, swap colours around to colour uvuv, and use red for uvu'v.

Either way, we've shown that the modified colouring of GvG-v has a larger set of distinct representatives than the original colouring. By repeating this process, we eventually find a colouring of GvG-v that has a full SDR — and therefore can be extended to a full Δ(G)+1Δ(G)+1-edge-colouring of GG.