Which 3-regular graphs are Schreier coset graphs?

Here are some usefull facts, and some historical details.

Every $2d$-regular graph (without loops of degree 1) is isomorphic to a Schreier graph.

The results for finite graphs is due to Gross. The result for locally finite graphs follows by compacity and was probably one of this well-known "folklore result" for long. To my knowledge, the first written proof of it can be found in "Some problems of the dynamics of group actions on rooted trees" by R. Grigorchuk 2011. But it has since be "reproven" many times (by J. Cannizzo in 2013, in my own phd thesis around the same time, ...).

A (2d+1)-regular graph (without loops of degree 1) is isomorphic to a Schreier graph if and only if it has a perfect matching.

This follows from the previous fact. See for example ARG's answer.

Every countable vertex transitive graphs is isomorphic to a Schreier graphs.

The finite case was done by C. Godsil and G. Royle in 2001. I did (circa 2013) the locally finite case in my phd thesis, using results of Aharoni on matchings in infinite graphs. I believe that an independant proof of it was published in 2016 by another author, but sadly cannot remember more details. Finally, the countable case was done by M. Hamman and A. Wendland in the appendix of https://arxiv.org/abs/2007.06432

Up to a double cover, any locally finite regular graphs is isomorphic to a Schreier graph.

See https://arxiv.org/pdf/2010.06431.pdf, which is intended as a small note for reference.

Here is the skeleton of the proof. Let $G$ be a locally finite graph. If $G$ is bipartite, put $K=G$. Otherwise, put $K=G\times C_2$. Then $K$ is connected, bipartite (and hence without loops of degree 1), regular and covers $G$. Since $K$ is bipartite and regular it has a perfect matching. The desired result follows.

[community wiki since it's my own question]

The answer is actually simple once the convention on degrees is clear (which it apparently was not at the time of writing)

Answer: If $k$ is odd, a $k$-regular loopless graph is a Schreiers graph if and only if it has a matching.

First note that elements $a \in S$ so that $a \neq a^{-1}$ necessarily create a 2 factor. There three cases (here $x$ is a vertex, or a coset):

(1) $a \cdot x = x$ this makes a loop and also a loop in the "reverse" direction since then $a^{-1} \cdot x =x$.

(2) $a \cdot a \cdot x = x$, this is an interesting case [and the main cause of my confusion], because it will often be displayed in the literature as a single-edge although there should be another edge coming from the fact that $a^{-1} \cdot a^{-1} \cdot x = x$

(3) $a$ makes a longer cycle before coming back to $x$.

If there are no loops then elements $a \in S$ so that $a = a^{-1}$ can only make a matching of the graph.

Hence, under the convention for degree taken, loopless Schreier graphs need to have a matching.

On the other hand, if you have a matching then you can label this matching by an element $b$ with $b=b^{-1}$. The rest of the graph is $2r$-regular for some $r$, so you can find $r$ disjoint $2$-factors and label them with $a_1,a_2,\ldots,a_r$.

My confusion came from diagrams such as the one below. Edge with arrows indicate how an element acts. Edge without arrow means the element switches both ends of that edge. This completely determine the action, but it gives a false impression on the vertex degree. In the picture below the vertices have degree 5 or 6 (depending on whether $c= c^{-1}$ or $c \neq c^{-1}$).