Vizing's theorem: Every simple non-directed graph is $(\Delta(G) + 1)$-edge-colorable.
The proof in the question is by induction on the number of vertex n. For n = 1, the statement is trivial. For n > 1, if v is a vertex of G, then by the induction hypothesis (G-v) is $(\Delta(G-v) + 1)$-edge-colorable. We can extend this coloring to v to form a proper $(\Delta(G) + 1)$-edge-coloring of G.
My idea for the algorithm is just to order the vertices by their degree, starting from the smallest, and then work with the vertices one by one, coloring the edges incident to it greedily (i.e. let say we use $[\Delta(G) + 1]$ to denote the colors, then for each edge we just try to use the smallest number possible).
This seems to work since at each step, with the current graph G', at most $\Delta(G') +1$ colours are used. But I can't prove the correctness of this, as well as its run-time complexity. I'd like to hear your opinion. Thanks.
Best Answer
The "proof" of Vizing's Theorem you're alluding to in the question doesn't make sense (or you've oversimplified it in your summary). In general, given a $(\Delta(G-v)+1)$-coloring of $G-v$, you can't always extend it to a $(\Delta(G)+1)$-coloring of $G$ without changing some colors on the edges of $G-v$. For example, suppose that $\Delta(G) = \Delta(G-v) = 4$, so that we're looking for a $5$-coloring, and the coloring of $G-v$ has the following colors on the neighbors of $v$:
There is clearly no way to extend this to a $5$-edge-coloring of all of $G$ without changing around some of the edges we've already colored. A true proof of Vizing's Theorem will give a way to do this; turning it into an algorithm will require carrying out a similar recoloring process sometimes.