Given a group $G$ and a subgroup $H$ the Schreier coset graph (w.r.t. some set $S$ of $G$) is the directed (and labelled) graph whose vertices are the cosets of $H$ (i.e. the set $G/H$) and $x \sim y$ if there is a $s \in S$ so that $x = sy$. 


When $S$ is symmetric (i.e. $s \in S \implies s^{-1} \in S$), then one can associate to this graph an undirected graph (by replacing the two edges with opposite directions and labels $a$ and $a^{-1}$ by an undirected edge). Note that it could happen that $a = a^{-1}$ which is unproblematic unless the edge makes a loop. So in the undirected graph one needs to distinguish the degree 2 loops (which come from $a$ and $a^{-1}$ acting trivially on the coset $x$) and the degree 1 loops (which come from $a = a^{-1}$ acting trivially on the coset $x$).


Using this construction (and this convention for loops), a Schreier graph is always a regular graph (of degree $|S|$).


Given an even degree regular graph (without "degree 1" loops), then it is possible to find a group $G$ (a free group actually), subgroup $H <G$ and set $S$ so that this graph is a Schreier coset graph. This is a result of J.L.Gross, see <https://doi.org/10.1016/0095-8956(77)90068-5>.


**Question:** Assume $\Gamma$ is a an 3-regular graph. What are the necessary conditions for $\Gamma$ to be a Schreier Graph?


I'm fine with any answers which assumes that $\Gamma$ is loopless. Sufficient conditions are somehow much more easy to come by (see examples below).


A combinatorial way to ask the question is to find a labelling of the directed graph underlying $\Gamma$ so that $a^{-1}$ always labels an edge in the opposite direction to $a$ (with the pesky exception of those degree 1 loops).


**Example** (of a sufficient condition for a loopless graph): if the graph has a perfect matching (a.k.a. 1-factor), then you can label these edges by an element $a = a^{-1}$. There only remains an even degree graph, so by the result of Gross you can get away with $G = F \* \mathbb{Z}\_2$ where $F$ is the free group mentioned above and $a$ is the generator (and only non-trivial element of $\mathbb{Z}\_2$).


**Example** (continued): every 3-regular bridgeless (i.e. without a cut-edge) graph has a 1-factor (a result of Petersen again). So every 3-regular bridgeless graph is a Schreier graph. In particular, the Petersen graph (or any other snark) are Schreier graphs.


Note that an element $a \in S$ so that $a \neq a^{-1}$ need not always label a 2-factor of $\Gamma$. It just needs to label a spanning subgraphs whose connected components are either edges or cycles (so a mix of 1-factor and 2-factor).


*[EDIT]*


**Non-example:** There is an example of an 3-regular graph which is not a Schreier graph. It's sometimes called the "no perfect matching graph", see <http://mathworld.wolfram.com/PerfectMatching.html> (you have to remove three edges in order to make the graph on that page 3-regular).


This non-example builds a lot on the fact that there are many bridges. 


*[EDIT]*


If there is a way to colour the edges in $k$-colours (and the graph is $k$-regular), then this gives a way to turn the graph in a Schreier graph. (Every element is so that $a = a^{-1}$ and the group $G$ is a free product of $k$ copies of $\mathbb{Z}\_2$.)


*[EDIT]*


It thought that a result of M.Kano see <https://doi.org/10.1016/0095-8956(86)90025-0> would give the necessary decomposition of the graph for odd degrees $\geq 5$, but this turns out to be incorrect.


Graphs which cannot be coloured are sometimes called of "class 2" (see Vizing's theorem). Although the Petersen graph (or any snark) is of "class 2", it is a Schreier graph (so being of class 1 is not a necessary condition).



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. An independant proof of it was published by Csoka and Lippner in 2017 <https://ems.press/journals/ggd/articles/14727>. 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.


