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.