{'fraction_non_alphanumeric': 0.03888805634647085, 'fraction_numerical': 0.010265248014386334, 'mean_word_length': 3.9396743153219838, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Up to a double cover, every regular connected graph is isomorphic to a Schreier graph

We prove that every connected locally finite regular graph has a double cover which is isomorphic to a Schreier graph.


Introduction
A central tool in combinatorial and geometric group theory is the notion of the Cayley graph of a group Γ, which is a graph that encodes the structure of the group, see Section 2 for all the relevant definitions. This construction is enlightening in two ways: on one hand it allows to see groups as geometric objects, while on the other hand it endows some graphs with an algebraic structure. In both direction, it permits a better understanding of the objects under consideration. It is therefore natural to ask which graphs can be realized as a Cayley graph of some group. This question has been answered in 1958 by Sabidussi [11] who showed that a connected graph G is isomorphic to a Cayley graph if and only if Aut(G) acts freely and transitively on the vertices of G.
It follows from Sabidussi's result that Cayley graphs are rather sparse among graphs, and thus too restrictive to study general graphs, even if we restrict ourself to the specific case of connected regular degree graphs. A more general notion of a "graph of algebraic origin" is hence needed. A suitable generalization of Cayley graphs, is the concept of a Schreier graph associated to a pair (Γ, Λ) where Λ is a subgroup of Γ (or equivalently associated to a transitive action of Γ on some set X). In this context, Cayley graphs correspond to pairs (Γ, {1}) (equivalently to free and transitive actions). Schreier graphs are always connected and of regular degree and one can thus wonder which connected graphs of regular degree are isomorphic to a Schreier graph.
The first step in this direction was made by Gross in his 1977 article [7], where he proved that every finite, connected regular graph of even degree is isomorphic to a Schreier graph. The result for infinite connected regular graphs of even degree follows by a compacity argument and was probably one of this well-known folklore result for long. A written proof of the infinite version can be found in [5], but it has since be rediscovered many times. On the other hand, it is easy to find examples, even finite ones, of connected regular graphs of odd degree that are not isomorphic to a Schreier graph, see the left of Figure 2. It hence remains to classify which connected regular graphs of odd degree are isomorphic to a Schreier graph. This question turns out to be equivalent to the existence of a perfect matching, an interesting subject in its own right, and also to the existence of a covering map to some particular graph, see Section 3. An interesting result in this direction is the fact that all transitive graphs (with at most countably many vertices and edges) are isomorphic to a Schreier graph. This fact was first proved by Godsil and Royle for finite graphs [4], then extended to locally finite graphs by the author [8], and finally to countable graphs by Hamann and Wendland in the appendix of [3].
Even if some connected regular graphs of odd degree are not isomorphic to a Schreier graph, one can still ask if they roughly "look like" a Schreier graph. One possible interpretation of the above is to ask for the existence of a finite degree covering from a Schreier graph to G. The aim of this note is to provide a proof of the following result, which concludes the above discussion.

Proposition 1. Let G be a dregular connected graph. Then either G is isomorphic to a Schreier graph or G has a double-cover H which is isomorphic to a Schreier graph.
While we were not able to find a reference to the above result in the literature, we do not claim any priority on it. In fact, this note was inspired by the following remark, which can be found at the end of Section 7 of [6]: "In fact up to the cover of degree 2 any regular graph can be realized as a Schreier graph [10]". However, [10] seems to treat only the case of graphs of even degree. Section 2 contains all the definitions as well as a discussion on the unusual concept of degenerated loop. The short Section 3 contains more materials on coverings and perfect matchings, as well as the proof of Proposition 1.
Since one of our motivations is the study of Schreier graphs, we will look at graphs in a broad sense. We allow multi-edges and loops as well as the less usual degenerated loops (also called half-edges, dangling edges or open edges).
Informally, a degenerated loop is the index 2 quotient of a path of length 1, see Figure 1. Heuristicaly it can either be seen as an edge with only one end, or as a loop that add only one to the degree. Allowing degenerated loops is necessary to treat the case of Schreier graphs of groups with generators of order 2.

Definition 2.
A graph is a 5-tuple (V, E, ι, τ, inv) where V and E are sets (of vertices and of arcs) and ι, τ : E → V and inv : E → E are applications (initial vertex, terminal vertex and inverse arc) such that ι · inv = τ , τ · inv = ι and inv is an involution.
There is a natural equivalence relation on arcs defined by e ∼ f if and only if e = f or e = inv( f ). The quotient set E/ ∼ is denoted by E and is the set of edges.
A vertex v and an edge e , in which case we also say the v is an end of e. An edge that is adjacent to only one vertex is called a loop.
Remark 3. Graph theorists usually forbid the existence of degenerated loops, but these special kinds of edges naturally arise in the context of Schreier graphs. Indeed, when allowing degenerated loops, there is a bijection between the subgroups of G (up to conjugacy) and graphs that are covered by Cayl(Γ; S), see [9] for a proof.
The degree of a vertex is the number of arcs e such that v = ι( e). In particular, a non degenerated loop adds 2 to the degree of its adjacent vertex, while a degenerated loop adds only 1. All graphs under consideration will be locally finite, that is the degree of any vertex is finite. Classical notions like paths and connected components are defined in a natural way. In particular, a bipartite graph has no loop. Finally, for a vertex v we define Star On pictures, we will represent degenerated loops by dotted line and other edges (including non-degenerated loops) by plain lines. A morphism of graph . A morphism ϕ : G → H between two graphs is a covering if all the induced map ϕ v are bijections. If moreover |ϕ −1 (v)| = 2 * for every vertex, then it is called a double cover. It is an easy exercise to show that every 2d-regular graph without degenerated loops covers a graph with 1 vertex and d loops.
Given a graph G = (V, E), its canonical double cover is the tensor product G ⊗ K 2 where K 2 has two vertices and an edge between them. That is, the vertex set of G ⊗ K 2 is V × {0, 1}, and an arc e from v to w is lifted to an arc from (v, 0) to (w, 1) and to an arc from (v, 1) to (w, 0). In particular, a non-degenerated loop adjacent to v is lifted to a pair of parallel edges between * The quantity |ϕ −1 (v)| depends only on the connected component of v.
(v, 0) and (v, 1), while a degenerated loop adjacent to v is lifted to a single edge between (v, 0) and (v, 1). See Figure 1. A simple verification shows that G ⊗ K 2 is a bipartite graph, which is a double cover of G. Moreover, G ⊗ K 2 is connected if and only if G is connected and not bipartite.

Definition 4.
A matching (also called a 1-factor) of a graph G is a subgraph M of G such that every vertex of M has degree 1 in M . A perfect matching is a matching of G that contains all vertices of G. A graph is matchable if it admits a perfect matching. Two matchings M 1 and M 2 are orthogonal if they share no edge.
Observe that not every regular graphs of odd degree are matchable, even among graphs without degenerated loop. See Figure 2. However, every vertextransitive graph of odd degree is matchable, [4,8]. We finally recall the definition of Schreier graphs.

Definition 5.
Let Γ be a group with a symmetric generating set S not containing the identity and let Λ be a subgroup of Γ. The corresponding (right) Schreier graph Schrei(Γ, Λ; S) is the graph with vertex set the right cosets {Λg | g ∈ Γ} and with an arc from Λg to Λh for every s in S such that Λgs = Λh. If X is a set with a transitive right action X Γ, the corresponding (right) orbital graph Schrei O (Γ, X; S) is the graph with vertex set X with an arc from x to y for every s in S such that x.s = y. If G is a (finitely generated) group, then it admits a (finite) generating system without element of order 2 if and only if it is not generalized dihedral [2]. Moreover, even for non-generalized dihedral group, it is sometimes natural to look at generating set containing elements of order 2. This is the main reason why we allow degenerated loops in our definition of a graph.

Coverings and matchability
First of all we have the following, which relates covers and perfect matchings: Lemma 6. Let G be a (2d + 1)-regular graph without degenerated loop. Then G is matchable if and only if it covers a graph with one vertex, one degenerated loop and d non-degenerated loops.
Proof. If ϕ : G → R is a covering and R has a degenerated loop e, then ϕ −1 (e) is a perfect matching of G.
On the other hand, let M be a perfect matching of G and G ′ the graph obtained by removing all edges of M from G. Then G ′ is 2d-regular without degenerated loop and hence covers R ′ a graph with one vertex and d nondegenerated loops. Let R be the graph obtained by adding a degenerated loop to R ′ . The covering G ′ ։ R ′ naturally extends to G ։ R by sending all edges of M to the degenerated loop of R.
As an easy generalization we obtain Corollary 7. Let G be a (2d + n)-regular graph without degenerated loop. Then G admits n pairwise orthogonal perfect matchings if and only if it covers a graph with one vertex, n degenerated loop and d non-degenerated loops.
By a theorem of Gross [7], every finite 2d-regular connected graph without degenerated loop is isomorphic to a Schreier graph of the free group F d . This result extends by compacity to infinite 2d-regular connected graph without degenerated loop, see [5] for a proof. On the other hand, Gross' Theorem does not carry over graphs of odd regular degree, see Figure 2. However, every connected transitive graph of degree 2d + 1 and without degenerated loop is isomorphic to a Schreier graph of F d * (Z/2Z), [4,8]. For general connected regular graphs, the situation is more complicated.

Lemma 8. Let G be a connected (2d + 1)-regular graph without degenerated loop. Then G is isomorphic to a Schreier graph if and only if it is matchable.
In this case it is isomorphic to a Schreier graph of F d * (Z/2Z), where F d is the free group of rank d.
A proof of this fact can be found in [8], but the result itself was probably already general knowledge at that time and essentially (at least for finite graphs) follows from [7]. A variation of Lemma 8 gives us Proposition 9 ([8]). Let G be a connected (2d + n)-regular graph without degenerated loop. Then G is isomorphic to a Schreier graph of F d * (Z/2Z) * n if and only if it has n perfect matchings that are pairwise orthogonal.
In order to prove Proposition 1, we will need the following fact, which follows (for example) from König's duality theorem for infinite bipartite graphs, [1]. It also follows, by compacity, from the similar statement for finite graphs.

Lemma 10. Every d-regular bipartite graph is matchable.
We now prove a more precise version of Proposition 1.

Lemma 11.
Let G be a d-regular connected graph. If G is bipartite, then it is isomorphic to a Schreier graph of (Z/2Z) * d . Otherwise, G ⊗ K 2 is isomorphic to a Schreier graph of (Z/2Z) * d .
Proof. If G = (V, E) is bipartite let K := G, while if G is not bipartite take K to be its canonical double cover. Now, the graph K is bipartite and d-regular. Let M 1 be a perfect matching of K and let K 1 be the graph obtained from K by removing the edges in M 1 . Then K 1 is bipartite of degree d − 1 and hence has a perfect matching M 2 as soon as d − 1 > 0. It is trivial that M 1 and M 2 are orthogonal. By repeating this we obtain d pairwise orthogonal perfect matchings. By Proposition 9 this implies that K is isomorphic to a Schreier graph of (Z/2Z) * d .
Corollary 12. Let G be a connected regular graph. Proof. This follows from Lemma 11 and the fact that a Schreier graph of (Z/2Z) * 2d (respectively of (Z/2Z) * (2d+1) ) without degenerated loop is isomorphic to a Schreier graph of F d (respectively of F d * (Z/2Z)), [8].
Observe that a Schreier graph is necessarily connected and of regular degree. On the other hand, there are examples of connected regular graphs of odd degree and without degenerated loop that are not isomorphic to a Schreier graph, see the left of Figure 2. There are also examples of connected regular graphs of even degree (but with at least one degenerated loop) that are not isomorphic to a Schreier graph, see the right of Figure 2. Finally, it isn't possible to ensure that G has a double cover isomorphic to a Schreier graph. Indeed, if T is a regular tree, then its only double cover is the disjoint union of two copies of T , which is not connected and hence not isomorphic to a Schreier graph. Hence, Proposition 1 is the "best possible" for locally finite graphs.