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).

"We prove that every connected locally finite regular graph has a double cover which is isomorphic to a Schreier graph". He mentions that the case of even degree was done in Lubotzky's book"Discrete groups, expanding graphs...". $\endgroup$ – YCor Oct 14 '20 at 6:18