About graphs whose edge set decomposes into perfect matchings
Yes: we call such graphs 1-factorable (a 1-factor is also known as a perfect matching). All such graphs are regular, but the converse is not true. In fact, a $d$-regular graph $G$ is 1-factorable if and only if it is of class one, that is, $\chi'(G) = d$, where $\chi'(G)$ is the chromatic index of $G$.

Deciding if a $d$-regular graph is of class 1 is NP-complete (see e.g. [1]), so you likely cannot test this efficiently.



[1] Leven, Daniel, and Zvi Galil. "NP completeness of finding the chromatic index of regular graphs." Journal of Algorithms 4.1 (1983): 35-44.