Can every d-regular graph be decomposed into at most d+1 matchings?

If so, how would you prove it? This arose in a circuit context: a paper I was reading considers applying a two-bit gate to every pair of vertices that share an edge in some arbitrary d-regular graph, and claims that the gates can be applied in at most d+1 layers. Hence, I am also curious whether such a decomposition can be computed efficiently.

This is Vizing's theorem: every graph with maximum degree $\Delta$ has a proper edge coloring with $\Delta+1$ colors. In particular, every $d$-regular graph has a $(d+1)$-edge-coloring.

In a proper edge coloring, two edges that share an endpoint must have different colors. As a result, if you look at all the edges of a color, they must form a matching. We used $d+1$ colors, so we have decomposed the graph into $d+1$ matchings.

We can do this efficiently, but the proof of Vizing's theorem is not easy (it is the hardest proof I've ever covered in an introductory graph theory class), and accordingly the algorithms are not straightforward. See the Misra & Gries edge-coloring algorithm on Wikipedia.

Some $d$-regular graphs admit a decomposition into only $d$ matchings, rather than $d+1$. (Of course, we can't do better, because all $d$ edges out of a vertex need to be in different matchings.) But in general, determining if we can shave off that one extra matching is NP-complete.