The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.
For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.
Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$.
Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.
Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.
Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.
This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$.
Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.
Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$).
The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component.
If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$.
Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.
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.
Best Answer
You have to go back to the definition of "improvement" of an edge coloring. They say that one $k$-edge coloring is an improvement on another if the sum of the number of colors at each vertex is greater. Then they say that a $k$-edge coloring is optimal if it cannot be improved on.
If the edge-chromatic number is greater than $\Delta+1$ then there must be an optimal $\Delta+1$-edge coloring that is not a proper edge coloring. Otherwise, we could keep improving any $\Delta+1$-edge coloring until the sum of the colors represented at the vertices is equal to the sum of the vertex degrees, at which point we have a proper $\Delta+1$-edge coloring.
The proof shows that an optimal $\Delta+1$-edge coloring that is not a proper edge coloring cannot exist, so $$\chi'\leq\Delta+1$$.