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]$.
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
Best Answer
Let $G$ be a bridgless planar $3$-regular graph and suppose it is given a plane embedding. Then by the four-colour theorem, there exists a proper $4$-face-colouring of $G$, say using $(1,2,3,4)$.
Now notice that since $G$ is bridge-less, all edges see two distinct faces which have different colours.
Colour the edges which see faces coloured $1,2$ or $3,4$ blue. Colour edges which see faces coloured $1,3$ or $2,4$ red. Colour the edges which see faces coloured $1,4$ or $2,3$. Note this colours all edges in our graph as every edge sees two distinct faces.
Since $G$ is $3$-regular, this colouring is a $3$-edge-colouring of $G$. If two adjacent edges were given the same colour, then either they both see the same coloured faces, or they each see two different faces.
In the case where both see the same coloured faces, this implies $G$ has a vertex of degree $2$. In the other case where the edges see all different faces, that implies that $G$ has a vertex with degree greater than $3$.