Vizing Theorem

Let be a Graph with
Then or

Proof

Clearly
WTS
Induction on edges
Pick an edge and colour everything else in
Construct the longest sequence of distinct
where if is missing colour then is coloured

Case 1

No such that is coloured
Note
Now recolour with colour

Case 2

for some
Recolour with for
leaving uncoloured, so WLOG
and is uncoloured with missing at
Let be a colour unused in
If is not in the same component as
then recolour that component
Similarly for
Now is a component containing
Note that is a path or an even cycle
But one of is missing at each of
so cannot exist.