Graph theory haiku | Page 4 of 4

Vizing’s Theorem

Induction on n.
Swap available colours
and find SDR.

Vizing’s theorem says:

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

The proof is by induction on the number of vertices; pick a vertex v and start with a (Δ(G)+1)-edge-colouring of G−v.

Ideally, we could just colour the edges around v and extend the edge-colouring to one of G. 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 v.

If we can’t find a full SDR, then we can still try to colour as many of v‘s edges as possible. Then, if an edge uv is still uncoloured, we can follow a proof of Hall’s Theorem to get a set of coloured edges u₁v, u₂v, …, u_kv such that:

uv can’t be coloured because there are fewer than k+1 total colours among those available at u and u₁, u₂, …, u_k in the colouring of G−v, but
if you un-colour any one of the edges and swap around the colours of the other ones, it would become possible to colour uv.

Note also that

regardless of how we assign Δ(G)+1 colours to edges of G, each vertex will have at least one colour left unused by the edges around it.

The first and third facts put together tell us that some colour (say, blue) is available at two vertices among u and u₁, u₂, …, u_k.

The second fact implies that any colour (e.g. red) still available at v can’t be available at any of the u_i, as otherwise we could swap around the colours to colour uv and then use red for u_iv.

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

We also know that there are two vertices among u, u₁, u₂, …, u_k that are incident with a red edge but not a blue one; those are also ends of paths in H. The paths might be the same as each other, and one might be the same as v‘s path, but the important thing is that we have a red-blue path where at least one of the ends is a neighbour u‘ of v and the other end is any vertex other than v.

We can now modify the colouring of G−v to swap red and blue along this path, which frees up red at u′. If u′ is u itself, then we can colour uv red; otherwise, we can uncolour u′v, swap colours around to colour uv, and use red for u′v.

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