On the structure of graphs which are locally indistinguishable from a lattice
Itai Benjamini\footnote{Department of Mathematics
Weizmann Institute of Science
Israel.
We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L^d$, the $d$-dimensional square lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L^d$, for each integer $d \geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They may be viewed as quotient lattices of $\mathbb{L^d$ in various compact orbifolds.) In the $d=2$ case, our methods yield new proofs of structure theorems of Thomassen \cite{thomassen-torus and of M\'arquez, de Mier, Noy and Revuelta \cite{noy, and also yield short, `algebraic' restatements of these theorems. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory. \vspace{0.2cm \noindent \footnotesize{MSC: Primary 05C75; Secondary 05C10.
1409.7587.tex
\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,verbatim,tikz}
\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{question}{Question}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{observation}{Observation}
\DeclareMathOperator{\Prob}{Prob}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Orb}{Orb}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\Aff}{Aff}
\DeclareMathOperator{\CT}{CT}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Cay}{Cay}
\DeclareMathOperator{\Image}{Image}
\newcommand{\Ld}{\mathbb{L}^d}
\DeclareMathOperator{\Link}{Link}
\DeclareMathOperator{\rank}{rank}
\newcommand{\Id}{\textrm{Id}}
\DeclareMathOperator{\cL}{\mathbb{L}}
\DeclareMathOperator{\Isom}{Isom}

\begin{document}

\title{On the structure of graphs which are locally indistinguishable from a lattice}
\author{Itai Benjamini\footnote{Department of Mathematics, Weizmann Institute of Science, Israel.}\,\, and David Ellis\footnote{School of Mathematical Sciences, Queen Mary, University of London, UK. Research supported in part by a Visiting Fellowship from the Weizmann Institute of Science.}}
\date{August 2015}
\maketitle

\begin{abstract}
We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional square lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d \geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They may be viewed as quotient lattices of $\mathbb{L}^d$ in various compact orbifolds.) In the $d=2$ case, our methods yield new proofs of structure theorems of Thomassen \cite{thomassen-torus} and of M\'arquez, de Mier, Noy and Revuelta \cite{noy}, and also yield short, `algebraic' restatements of these theorems. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory.
\vspace{0.2cm}

\noindent \footnotesize{MSC: Primary 05C75; Secondary 05C10.}
\end{abstract}

\section{Introduction}
A great number of results in combinatorics concern the impact of `local' properties on `global' properties of structures. Some of these results concern the global properties of {\em all} structures with a given local property. Others concern the `typical' global properties of a `random' structure with a given local property. As an example of the former, Dirac's classical theorem \cite{dirac} states that in any $n$-vertex graph where each vertex has degree at least $n/2$, there exists a Hamiltonian cycle. On the other hand, the literature on random graphs contains many examples of the latter, among which is the following. Let $n,d \in \mathbb{N}$ with $n > d \geq 3$ and $nd$ even, and let $G_d(n)$ denote the (random) graph chosen uniformly from the set of all $d$-regular graphs with vertices $\{1,2,\ldots,n\}$; $G_d(n)$ is called the {\em random (labelled) $d$-regular graph}. It was proved by Bollob\'as in \cite{bollobas-connected} and independently by Wormald in \cite{wormald-thesis} that for any fixed integer $d \geq 3$, $G_d(n)$ is connected with high probability, meaning that
\begin{equation}\label{eq:d-connected} \Prob\{G_d(n)\textrm{ is }d\textrm{-connected}\} \to 1 \quad \textrm{as } n \to \infty.\end{equation}
Moreover, it was proved by Bollob\'as in \cite{bollobas-cycles} and independently by Wormald in \cite{wormald-thesis} that for any fixed integers $d,g \geq 3$,
\begin{equation}\label{eq:short-cycles}\textrm{Prob}\{\textrm{girth}(G_d(n)) \geq g\} = (1+o(1)) \frac{\exp(-\sum_{l=1}^{g-1} \lambda_l)}{1-\exp(-(\lambda_1+\lambda_2))},\end{equation}
where
$$\lambda_i = \frac{(d-1)^i}{2i} \quad (i \in \mathbb{N}),$$
and it was proved by Bollob\'as in \cite{bollobas} and independently by McKay and Wormald in \cite{wormald-mckay} that for any fixed integer $d \geq 3$,
\begin{equation}\label{eq:asym}\Prob\{|\Aut(G_d(n))| = 1\} \to 1 \quad \textrm{as } n \to \infty,\end{equation}
where $\Aut(G)$ denotes the automorphism group of a graph $G$.

It is natural to ask what happens to the global structure of a graph if we impose a `local' condition which is stronger than being $d$-regular. A natural condition to impose is that the subgraph induced by the ball of radius $r$ in $G$ around any vertex, is isomorphic to some fixed graph.

To make this precise, we introduce some notation and definitions. If $G = (V,E)$ is a graph, and $v,w$ are vertices of $G$, the {\em distance from $v$ to $w$ in $G$} is defined to be the minimum number of edges in a path from $v$ to $w$ in $G$; it is denoted by $d_{G}(v,w)$. (If $v$ and $w$ are in different components of $G$, then we define $d_G(v,w) = \infty$.) Similarly, if $v$ is a vertex of $G$ and $e$ is an edge of $G$, the {\em distance from $v$ to $e$ in $G$} is defined to be $\min\{d_G(v,x),d_G(v,y)\}$, where $e=xy$. If $G$ is a graph, and $v$ is a vertex of $G$, the {\em ball of radius $r$ around $v$} is the set of vertices of $G$ of distance at most $r$ from $v$; it is denoted by $B_{r}(v,G)$. In symbols,
$$B_r(v,G) := \{w \in V(G):\ d_{G}(v,w) \leq r\}.$$
We write $\Link_r(v,G)$ for the subgraph of $G$ induced by the vertices in $B_{r}(v,G)$; equivalently, $\Link_r(v,G)$ is the subgraph of $G$ consisting of all the vertices and edges of $G$ that have distance at most $r$ from $v$. Similarly, we define $\Link_r^{-}(v,G)$ to be the subgraph of $G$ consisting of the vertices of $G$ with distance at most $r$ from $v$, and the edges of $G$ with distance less than $r$ from $v$. Equivalently,
$$\Link_r^{-}(v,G) = \Link_r(v,G) \setminus \{xy \in E(G):\ d(v,x)=d(v,y)=r\}.$$
A {\em rooted graph} is an ordered pair $(G,v)$ where $G$ is a graph, and $v$ is a vertex of $G$.

We can now state our key definitions.

\begin{definition}
\label{defn:r-locally}
If $(F,u)$ is a rooted graph, we say that a graph $G$ is {\em $r$-locally $(F,u)$} if for every vertex $v \in V(G)$, there exists a graph isomorphism $\phi: \Link_r(u,F) \to \Link_r(v,G)$ such that $\phi(u)=v$.
\end{definition}

\begin{definition}
\label{defn:weakly-r-locally} If $(F,u)$ is a rooted graph, we say that a graph $G$ is {\em weakly $r$-locally $(F,u)$} if for every vertex $v \in V(G)$, there exists a graph isomorphism $\phi: \Link_r^{-}(u,F) \to \Link_r^{-}(v,G)$ such that $\phi(u)=v$.
\end{definition}

Clearly, we have the implications
\begin{align*} G \textrm{ is } r\textrm{-locally }(F,u) & \Rightarrow G \textrm{ is weakly } r\textrm{-locally }(F,u)\\
& \Rightarrow G \textrm{ is }(r-1)\textrm{-locally }(F,u),\end{align*}
for any $r \in \mathbb{N}$.

We remark that if we view graphs as 1-dimensional simplicial complexes, equipped with the metric defined by extending the graph distance linearly along edges, then $\Link_r(v,G)$ is the set of points of metric-distance at most $r+1/2$ from $v$, and $\Link_r^{-}(v,G)$ is the set of points of metric-distance at most $r$ from $v$. Hence, Definitions \ref{defn:r-locally} and \ref{defn:weakly-r-locally} are natural from a topological point of view.

We remark also that if $F$ is vertex-transitive, then Definitions \ref{defn:r-locally} and \ref{defn:weakly-r-locally} are independent of the choice of $u$. Hence, if $F$ is a vertex-transitive graph, we say that a graph $G$ is {\em $r$-locally $F$} if there exists $u \in V(F)$ such that $G$ is $r$-locally $(F,u)$ (or equivalently, if for all $u \in V(F)$, $G$ is $r$-locally $(F,u)$.) Similarly, we say that $G$ is {\em weakly $r$-locally $F$} if there exists $u \in V(F)$ such that $G$ is weakly $r$-locally $(F,u)$.

As a simple example, let $T_d$ denote the infinite $d$-regular tree. A graph $G$ is $r$-locally $T_d$ if and only if it is a $d$-regular graph with girth at least $2r+2$, and is weakly $r$-locally $T_d$ if and only if it is a $d$-regular graph with girth at least $2r+1$.

We note that for a fixed integer $r$ and a fixed rooted graph $(F,u)$, the question of whether or not there exists a graph which is $r$-locally $F$ is highly non-trivial, even in the case $r=1$, where it has been rather intensively studied. If $G$ is a graph and $v$ is a vertex of $G$, we write $\Gamma(v)$ for the set of neighbours of $v$, and we write $L(v,G)$ for the subgraph of $G$ induced by the neighbours of $v$, i.e. $L(v,G) = G[\Gamma(v)]$. The graph $L(v,G)$ is often called the {\em link of $G$ at $v$}. Note that a graph $G$ is $1$-locally $(F,u)$ if and only if $L(v,G) \cong L(u,F)$ for every vertex $v$ of $G$. (Graphs which are $1$-locally-$(F,u)$ for some rooted graph $(F,u)$ are usually called {\em graphs of constant link}.) Bulitko \cite{bulitko} proved that there is no decision algorithm which, given a finite graph $H$, determines whether there is a (possibly infinite) graph $G$ having constant link $H$. The question of algorithmic decidability remains open if `possibly infinite' is replaced by `finite'.

Several authors have given succinct necessary or sufficient conditions on $H$ for there to exist finite (or, in some cases, possibly infinite) graphs of constant link $H$, for graphs $H$ within various classes; results of this kind can be found in \cite{brown-connelly}, \cite{hubaut}, \cite{bugata}, \cite{busset}, \cite{doyen}, \cite{hall-1}, \cite{hall-2}, \cite{hall-3}, \cite{hall-4}, \cite{sedlacek}, \cite{zelinka-1}, and \cite{zelinka-2}. However, the problem seems very hard in general. For more background, the reader may consult the survey \cite{hell}. To demonstrate that the `finite' and `infinite' questions are very different, we recall from \cite{brown-connelly} that if $H$ is a vertex-disjoint union of one 1-edge path and two 2-edge paths, then no finite graph has constant link $H$, but there exists an infinite graph which has constant link $H$, and which is vertex-transitive. On the other hand, the only connected graph which has constant link $K_t$, is the complete graph $K_{t+1}$.

In this paper, we will focus on the case where $F$ is a Euclidean lattice. If $d \in \mathbb{N}$, the {\em $d$-dimensional lattice} $\mathbb{L}^d$ is the graph with vertex-set $\mathbb{Z}^d$, and edge-set
$$\{\{x,x+e_i\}:\ x \in \mathbb{Z}^d, i \in [d]\},$$
where $e_i = (0,0,\ldots,0,1,0,\ldots,0)$ denotes the $i$th unit vector in $\mathbb{R}^d$. We study the properties of graphs which are $r$-locally $\mathbb{L}^d$ or weakly $r$-locally $\mathbb{L}^d$, for various $r$. It turns out that for all $d \in \mathbb{N}$ and all $r \geq 3$, graphs which are weakly $r$-locally $\mathbb{L}^d$ have a very rigidly proscribed, `algebraic' global structure, in stark contrast to a uniform random $d$-regular graph, which can be generated using a simple, purely combinatorial process (namely, the Configuration Model of Bollob\'as \cite{config}).

Note that a graph is $r$-locally $\mathbb{L}^1$ if and only if it is a vertex-disjoint union of cycles, each of length at least $2r+2$, and is weakly $r$-locally $\mathbb{L}^1$ if and only if it is a vertex-disjoint union of cycles, each of length at least $2r+1$. Hence, the first interesting case is $d=2$, where we prove the following.

\begin{theorem}
\label{thm:cover-2}
Let $G$ be a connected graph which is weakly $2$-locally $\mathbb{L}^2$. Then there exists a normal covering map\footnote{See section 2 for the definition of a normal covering map.} from $\mathbb{L}^2$ to $G$.
\end{theorem}

This yields a new proof of a structure theorem of M\'arquez, de Mier, Noy and Revuelta \cite{noy} (under a slightly weakened hypothesis), as well as a short, `algebraic' restatement of their theorem; see section 5 for a discussion of this connection. Our proof of Theorem \ref{thm:cover-2} (in section 3) goes via a direct construction of a covering map; it has the advantage of generalising (under a slightly stronger hypothesis) to the case of $\mathbb{L}^d$ for $d \geq 3$. Note that Theorem \ref{thm:cover-2} includes the case of infinite connected graphs which are weakly $2$-locally-$\mathbb{L}^2$ (these are necessarily countably infinite).

In section 4, we prove a slight strengthening of the finite-graph case of Theorem \ref{thm:cover-2}, using a more geometric argument. (This yields a new proof of a structure theorem of Thomassen, Theorem 4.1 in \cite{thomassen-torus} --- see section 5.) To state it, we need a preliminary definition, implicit in \cite{thomassen-torus}.

\begin{definition}
Let $G$ be a graph. We say that $G$ has the {\em 4-cycle wheel property} if it is 4-regular, and there exists a family $\mathcal{C}$ of 4-cycles of $G$ such that for every vertex $v$ of $G$, there are exactly four 4-cycles in $\mathcal{C}$ which contain $v$, and the union of these four 4-cycles is isomorphic to the following graph.
\end{definition}

\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=6pt,inner sep=0pt]
\draw (0,0) node {};
\draw (0,1) node {};
\draw (0,-1) node {};
\draw (-1,0) node {};
\draw (1,0) node {};
\draw (1,1) node {};
\draw(-1,1) node {};
\draw (-1,-1) node {};
\draw (1,-1) node {};
\draw (-1,0) -- (0,0) -- (1,0);
\draw (0,-1) -- (0,0) -- (0,1);
\draw (-1,0) -- (-1,1) -- (0,1) -- (1,1) -- (1,0) -- (1,-1) -- (0,-1) -- (-1,-1) -- (-1,0);
\end{tikzpicture}
\end{center}

Note that a graph which is weakly $2$-locally $\mathbb{L}^2$ has the 4-cycle wheel property; on the other hand, a $3 \times 3$ discrete torus has 4-cycle wheel property, but is not weakly $2$-locally $\mathbb{L}^2$. Hence, the 4-cycle wheel property is strictly weaker than the property of being weakly 2-locally $\mathbb{L}^2$. We prove the following analogue of Theorem \ref{thm:cover-2} for graphs with the 4-cycle wheel property.

\begin{theorem}
\label{thm:cover-wheel}
Let $G$ be a finite, connected graph with the 4-cycle wheel property. Then there exists a normal covering map from $\mathbb{L}^2$ to $G$.
\end{theorem}

It is a well-known fact in topological graph theory that if a finite graph $G$ is normally covered by a graph $F$, then $G$ is isomorphic to the quotient graph $F/\Gamma$ for some subgroup $\Gamma$ of $\Aut(F)$ which acts freely on $F$. (See Definitions \ref{definition:free-action} and \ref{definition:quotient} in section 2 for the definitions of a quotient graph and a free action.) Using this fact, we deduce that if $G$ is a finite, connected graph with the 4-cycle wheel property, then $G$ is isomorphic to a quotient of $\mathbb{L}^2$ by a finite-index subgroup of $\Aut(\mathbb{L}^2)$ with minimum displacement at least 3. (If $F$ is a graph and $\Gamma \leq \Aut(F)$, the {\em minimum displacement} of $\Gamma$ is defined to be $D(\Gamma) : = \min\{d_F(x,\gamma(x)):\ x \in V(F),\ \gamma \in \Gamma \setminus \{\Id\}\}$.)

It is a straightforward exercise in group theory to determine the finite-index subgroups of $\Aut(\mathbb{L}^2)$ of minimum displacement at least 3: each such subgroup $\Gamma$ is either:
\begin{enumerate}
\item[(1)] generated by two linearly independent translations, or
\item[(2)] generated by one `glide-reflection'\footnote{A {\em glide reflection} is an isometry of $\mathbb{R}^2$ of the form $r \circ t$, where $t$ is a translation and $r$ is a reflection in an axis parallel to the direction of the translation $t$.} and one translation in a direction perpendicular to the reflection-axis of the glide reflection.
\end{enumerate}
It is easy to see that we can uniquely extend each automorphism of $\mathbb{L}^2$ to an isometry of $\mathbb{R}^2$, so we can view each subgroup $\Gamma \leq \Aut(\mathbb{L}^2)$ as a subgroup of $\Isom(\mathbb{R}^2)$, the group of isometries of the Euclidean plane; the cases (1) and (2) correspond to the two classes of 2-dimensional {\em Bieberbach groups}\footnote{A {\em Bieberbach group} is a torsion-free crystallographic group; see Definition \ref{definition:crystallographic} in section 2 for the definition of a crystallographic group.}, and the corresponding orbit space $\mathbb{R}^2 /\Gamma$ is a torus in case (1), and a Klein bottle in case (2). This yields the following.

\begin{corollary}
\label{corr:torusklein2}
Let $G$ be a finite, connected graph with the 4-cycle wheel property. Then $G$ is isomorphic to $\mathbb{L}^2/\Gamma$, where $\Gamma \leq \Aut(\mathbb{L}^2) \leq \Isom(\mathbb{R}^2)$ is such that $\mathbb{R}^2/\Gamma$ is either a torus or a Klein bottle.
\end{corollary}

Hence, we can view any finite, connected graph with the 4-cycle wheel property as a `quotient lattice' of $\mathbb{L}^2$ inside a torus or a Klein bottle; in particular, it must be a quadrangulation of the torus or of the Klein bottle, as observed by Thomassen in \cite{thomassen-torus}.

For dimension $d \geq 3$, we prove the following.

\begin{theorem}
\label{thm:cover-d}
Let $d \geq 3$ be an integer, and let $G$ be a connected graph which is weakly $3$-locally $\mathbb{L}^d$. Then there exists a normal covering map from $\mathbb{L}^d$ to $G$. 
\end{theorem}

We will give a construction (Example \ref{example:Ld}) to show that Theorem \ref{thm:cover-d} is best possible, in the sense that for any $d \geq 3$, there exist finite connected graphs which are 2-locally $\mathbb{L}^d$ but which are not covered by $\mathbb{L}^d$. The construction is algebraic.

Similarly to in the $d=2$ case, we can deduce from Theorem \ref{thm:cover-d} that a connected graph $G$ is weakly $3$-locally $\mathbb{L}^d$ if and only if $G$ is isomorphic to a quotient of $\mathbb{L}^d$ by a subgroup of $\Aut(\mathbb{L}^d)$ which has minimum displacement at least 7. Since we can uniquely extend any automorphism of $\mathbb{L}^d$ to an isometry of $\mathbb{R}^d$, we can also view each subgroup $\Gamma \leq \Aut(\mathbb{L}^d)$ as a subgroup of $\Isom(\mathbb{R}^d)$; if $G$ is finite, then the corresponding subgroup $\Gamma \leq \Isom(\mathbb{R}^d)$ is a {\em $d$-dimensional crystallographic group}. Unlike in the $d=2$ case, the corresponding subgroup $\Gamma$ is not necessarily torsion-free, and we shall see that, for each $d \geq 7$, the orbit space $\mathbb{R}^d/\Gamma$ need not be a topological manifold (see Remark \ref{remark:not-manifold}); rather, it is a compact {\em (topological) orbifold}. This yields the following.

 \begin{corollary}
 \label{corr:structure-d}
 Let $d \geq 3$ be an integer, and let $G$ be a finite, connected graph which is weakly $3$-locally $\mathbb{L}^d$. Then $G$ is isomorphic (as a graph) to the quotient lattice $\mathbb{L}^d/\Gamma$ in the compact topological orbifold $\mathbb{R}^d/\Gamma$, where $\Gamma$ is a $d$-dimensional crystallographic group which restricts to a group of automorphisms of $\mathbb{L}^d$.
  \end{corollary}

\begin{remark}
Bieberbach's theorems (\cite{bieberbach-1911}, \cite{bieberbach-1912}) imply that for any $d \in \mathbb{N}$, there are only a finite number ($f(d)$, say) of affine-conjugacy classes of $d$-dimensional crystallographic groups (where two crystallographic groups are said to be {\em affine-conjugate} if they are conjugate via an affine transformation of $\mathbb{R}^d$). It follows that the orbit space $\mathbb{R}^d/\Gamma$ in Corollary \ref{corr:structure-d} is homeomorphic to one of at most $f(d)$ topological spaces. (See Fact \ref{fact:bieberbach}.)
\end{remark}

We note that many authors have exhibited connections between graphs with constant link and algebraic topology; see for example \cite{nedela}, \cite{nedela-2}, \cite{perkel}, \cite{perkel-2}, \cite{ronan}, \cite{surowski} and \cite{vince}. However, to the best of our knowledge, the above results on coverings by $\mathbb{L}^d$ are new, and we are not aware of any other structure theorems for graphs which are $r$-locally-$\mathbb{L}^d$, for $d \geq 3$. As noted in \cite{noy}, the methods of \cite{noy} and \cite{thomassen-torus} seem to be specific to the case $d=2$.

This paper deals with the properties of {\em all} finite graphs which are $r$-locally $\mathbb{L}^d$, or weakly $r$-locally $\mathbb{L}^d$, for various $r$. In a subsequent paper \cite{in-preparation}, we will study the {\em typical} properties of a uniform random $n$-vertex graph which is $r$-locally $\mathbb{L}^d$. It turns out that, for any integer $r \geq 2$, a graph chosen uniformly at random from the set of all $n$-vertex graphs which are $r$-locally $\mathbb{L}^2$, has largest component of size $o(n)$, with high probability. Similarly, for any integer $d \geq 3$ and any integer $r \geq 3$, a graph chosen uniformly at random from the set of all $n$-vertex graphs which are $r$-locally $\mathbb{L}^d$, has largest component of size $o(n)$, with high probability. This is in stark contrast with a random $(2d)$-regular graph on $n$ vertices, which is connected with high probability for all $d \geq 2$, by (\ref{eq:d-connected}). Similarly, it is in contrast with a uniform random $n$-vertex graph which is $1$-locally $\mathbb{L}^d$, as this is precisely a random $(2d)$-regular graph, conditioned on having no cycles of length 3, so is connected with high probability, by (\ref{eq:d-connected}) and (\ref{eq:short-cycles}). (We remark that all the statements in this paragraph hold true regardless of whether the $n$-vertex graphs are labelled or unlabelled.) In \cite{in-preparation}, we make several conjectures regarding what happens when $\mathbb{L}^d$ is replaced by other Cayley graphs of finitely generated groups.

The remainder of this paper is structured as follows. In section 2, we give the definitions, background and standard tools which we require from topological graph theory, topology and group theory. This section is rather long, but as various `standard' texts in topology and geometry use slightly different conventions, we prefer to set out our conventions in full, to avoid ambiguity. All or part of section 2 can be skipped by readers familiar with the relevant areas. In section 3, we prove Theorems \ref{thm:cover-2} and \ref{thm:cover-d}, by direct constructions of the required normal covering maps, and we give an example showing that Theorem \ref{thm:cover-d} is best possible in a certain sense. In section 4, we prove Theorem \ref{thm:cover-wheel}, using a more geometrical argument. In section 5, we deduce Corollary \ref{corr:torusklein2} from Theorem \ref{thm:cover-wheel} and Corollary \ref{corr:structure-d} from Theorem \ref{thm:cover-d}, using some fairly standard arguments from topological graph theory and group theory; we then discuss some prior results and their relation to our results. We conclude with some open problems.

 \section{Definitions, background and tools}
 \label{subsection:defns}
 \begin{comment} We use the Landau notation for functions. Namely, if $X$ is a set, and $f,g:X \to \mathbb{R}$ are functions, then we write $g = O(f)$ if there exists an absolute constant $C>0$ such that $|g(x)| \leq C|f(x)|$ for all $x \in X$. We write $g = \Omega(f)$ if there exists an absolute constant $c>0$ such that $|g(x)| \geq c|f(x)|$ for all $x \in X$. We write $g = \Theta(f)$ if $g = O(f)$ and $g = \Omega(f)$ both hold.\end{comment}
 
 \subsubsection*{Basic graph-theoretic notation}
 
 Unless otherwise stated, all graphs will be {\em simple} (that is, without loops or multiple edges). They need not be finite (unless this is explicitly stated). If $G$ is a graph, we write $V(G)$ for the vertex-set of $G$ and $E(G)$ for the edge-set of $G$. If $S \subset V(G)$, we let $N(S)$ denote the {\em neighbourhood} of $S$, i.e.
$$N(S) = S \cup \{v \in V(G):\ \{s,v\} \in E(G)\textrm{ for some } s \in S\},$$
and we define
$$\Gamma(S) := N(S) \setminus S.$$
In particular, if $v \in V(G)$, $\Gamma(v): = \Gamma(\{v\})$ denotes the set of neighbours of $v$.

We say a graph $G$ is {\em locally finite} if every vertex of $G$ has only finitely many neighbours.

A graph $G$ is said to be {\em connected} if for any two vertices $u,v \in V(G)$, there exists a path in $G$ from $u$ to $v$ of finite length. The maximal connected subgraphs of $G$ are called the {\em components} of $G$. If $G$ is a graph, and $u,v \in V(G)$ are in the same component of $G$, the {\em distance from $u$ to $v$ in $G$} is the minimum length of a path from $u$ to $v$; it is denoted by $d_{G}(u,v)$ (or by $d(u,v)$, when the graph $G$ is understood). A path of minimum length between $u$ and $v$ (i.e., a path of length $d_{G}(u,v)$) is called a {\em geodesic}.

\subsubsection*{Background and tools from topological graph theory}
We follow \cite{gross-tucker} and \cite{nedela-survey}.

\begin{definition}
If $F$ and $G$ are graphs, and $p:V(F) \to V(G)$ is a graph homomorphism from $F$ to $G$, we say that $p$ is a {\em covering map} if $p$ maps $\Gamma(v)$ bijectively onto $\Gamma(p(v))$, for all $v \in V(F)$. In this case, we say that $F$ {\em covers} $G$.
\end{definition}

\begin{remark}
\label{remark:surjective}
It is easy to see that if $F$ and $G$ are graphs with $G$ connected, and $p:V(F) \to V(G)$ is a covering map, then $p$ is surjective.
\end{remark}

\begin{definition}
Let $F$ and $G$ be graphs, and let $p:V(F) \to V(G)$ be a covering of $G$ by $F$. The pre-image of a vertex of $G$ under $p$ is called a {\em fibre} of $p$.
\end{definition}

\begin{definition}
Let $F$ and $G$ be graphs, and let $p:V(F) \to V(G)$ be a covering of $G$ by $F$. An automorphism $\phi \in \Aut(F)$ is said to be a {\em covering transformation of $p$} if $p \circ \phi = p$. The group of covering transformations of $p$ is denoted by $\CT(p)$.
\end{definition}

Note that any covering transformation of $p$ acts on each fibre of $p$, but it need not act transitively on any fibre of $p$.

\begin{definition}
Let $F$ and $G$ be graphs, and let $p:V(F) \to V(G)$ be a covering of $G$ by $F$. We say that $p$ is a {\em normal} covering if $\CT(p)$ acts transitively on each fibre of $p$.
\end{definition}

\begin{remark}
It is well known (and easy to check) that if $F$ is a connected graph, and $p:V(F) \to V(G)$ is a covering of $G$ by $F$, then if $\CT(p)$ acts transitively on some fibre of $p$, it acts transitively on every fibre of $p$. Hence, in the previous definition, `on each fibre' may be replaced by `on some fibre'.
\end{remark}

\begin{definition}
Let $F$ and $G$ be graphs. Suppose $p:V(F) \to V(G)$ is a covering map from $F$ to $G$. Let $W$ be a walk in $G$, meaning a finite sequence $(w_0,w_1,\ldots,w_l)$ of vertices of $G$ with $\{w_i,w_{i+1}\} \in E(G)$ for all $i \in \{0,1,\ldots,l-1\}$. If $W' = (x_0,x_1,\ldots,x_l)$ is a walk in $F$ such that $p(x_i) = w_i$ for all $i \in [l]$, we say that $W'$ is a {\em lift} of $W$ and that $W$ is a {\em projection} of $W'$.
\end{definition}

\begin{remark}(The unique walk-lifting property.)
\label{remark:unique-lift}

It follows easily from the definition of a covering that if $W$ is a walk in $G$, starting at a vertex $w \in V(G)$, then for any vertex $x \in V(F)$ with $p(x) = w$, there exists a unique lift of $W$ to $F$ which starts at $x$.
\end{remark}

\begin{definition}
Let $\Gamma$ be a group, let $X$ be a set, and let $\alpha:\Gamma \times X \to X$ be an action of $\Gamma$ on $X$. For each $x \in X$, we write $\Orb_{\Gamma}(x): = \{\gamma(x):\ \gamma \in \Gamma\}$ for the $\Gamma$-orbit of $x$, and $\Stab_{\Gamma}(x) := \{\gamma \in \Gamma:\ \gamma(x)=x\}$ for the stabiliser of $x$ in $\Gamma$. When the group $\Gamma$ is understood, we suppress the subscript $\Gamma$.
\end{definition}

\begin{definition}
If $F$ is a graph and $\Gamma \leq \Aut(F)$, the {\em minimum displacement} of $\Gamma$ is defined to be $D(\Gamma) : = \min\{d_F(x,\gamma(x)):\ x \in V(F),\ \gamma \in \Gamma \setminus \{\Id\}\}$.
\end{definition}

\begin{definition}
\label{definition:free-action}
Let $\Gamma$ be a group, let $X$ be a set, and let $\alpha:\Gamma \times X \to X$ be an action of $\Gamma$ on $X$. We say that $\alpha$ is {\em free} if $\alpha(g,x) \neq x$ for all $x \in X$ and all $g \in \Gamma \setminus \{\textrm{Id}\}$.
\end{definition}

\begin{definition}(Quotient of a graph.)
\label{definition:quotient}

Let $F$ be a simple graph, and let $\Gamma \leq \Aut(F)$. Then $\Gamma$ acts on $V(F)$ via the natural left action $(\gamma,x) \mapsto \gamma(x)$, and on $E(F)$ via the natural (induced) action $(\gamma,\{x,y\}) \mapsto \{\gamma(x),\gamma(y)\}$. We define the {\em quotient graph} $F/\Gamma$ to be the multigraph whose vertices are the $\Gamma$-orbits of $V(F)$, and whose edges are the $\Gamma$-orbits of $E(F)$, where for any edge $\{x,y\} \in E(F)$, the edge $\Orb(\{x,y\})$ has endpoints $\Orb(x)$ and $\Orb(y)$. Note that $F/\Gamma$ may have loops (if $\{x,\gamma(x)\} \in E(F)$ for some $\gamma \in \Gamma$ and some $v \in V(F)$), and it may also have multiple edges (if there exist $\{u_1,u_2\},\{v_1,v_2\} \in E(F)$ with $\gamma_1(u_1) = v_1$ and $\gamma_2(u_2) = v_2$ for some $\gamma_1,\gamma_2 \in \Gamma$, but $\{\gamma(u_1),\gamma(u_2)\} \neq \{v_1,v_2\}$ for all $\gamma \in \Gamma$).
\end{definition}

\begin{definition}
Let $G$ be a graph, and let $\Gamma \leq \Aut(G)$. We say that $\Gamma$ {\em acts freely on $G$} if the natural actions of $\Gamma$ on $V(G)$ and $E(G)$ are both free actions, or equivalently, if no element of $\Gamma \setminus \{\Id\}$ fixes any vertex or edge of $G$. 
\end{definition}

The following is an instance of a well-known general statement in topology; for completeness, we provide a proof in the graph case.

\begin{lemma}
\label{lemma:free}
Let $F$ be a connected (possibly infinite) graph, let $G$ be a graph, and let $p:V(F) \to V(G)$ be a covering map from $F$ to $G$. Then $\CT(p)$ acts freely on $F$.
\end{lemma}

\begin{proof}
We first show that $\CT(p)$ acts freely on $V(F)$. Suppose $\phi \in \CT(p)$ with $\phi(y)=y$ for some $y \in V(F)$. Let $z \in V(F) \setminus \{y\}$; we must show that $\phi(z)=z$. Let $P$ be a path in $F$ from $y$ to $z$. Then $\phi(P)$ is a walk in $F$ starting at $y$ and with $p(\phi(P)) = p(P)$, i.e., $\phi(P)$ and $P$ project to the same walk in $P$. By the unique walk-lifting property (Remark \ref{remark:unique-lift}), we must have $\phi(P)=P$, so in particular $\phi(z)=z$. Hence, $\phi = \Id$.

We now show that $\CT(p)$ acts freely on $E(F)$. Suppose for a contradiction that there exists $\phi \in \CT(p) \setminus \{\Id\}$ with $\{\phi(x),\phi(y)\} = \{x,y\}$ for some $\{x,y\} \in E(F)$. Since $\CT(p)$ acts freely on $V(F)$, we must have $\phi(x)=y$ and $\phi(y)=x$. Hence, $p(x)=p(y)$. But this contradicts the fact that $p$ is bijective on $N(x)$.
\end{proof}

The following key lemma connects normal coverings with quotients. Again, it is an instance of a well-known general statement in topology, but for completeness, we provide a simple proof in the graph case.
\begin{lemma}
\label{lemma:iso}
Let $F$ and $G$ be simple graphs with $G$ connected, and suppose $p:V(F) \to V(G)$ is a normal covering map from $F$ to $G$. Then there is a graph isomorphism between $G$ and $F/\CT(p)$.
\end{lemma}

\begin{proof}
First, we check that $F/\CT(p)$ is a simple graph. If it contains a loop, then there exists an edge $\{x,y\} \in E(F)$ and $\phi \in \CT(p)$ such that $y=\phi(x)$, but then $p(y) = p(\phi(x))=p(x)$, contradicting the fact that $p$ is bijective on $N(x)$. Suppose for a contradiction that $F/\CT(p)$ has a multiple edge. Then there exist edges $\{x,y\},\{u,v\} \in E(F)$ with $\phi(x)=u$ and $\phi'(y)=v$ for some $\phi,\phi' \in \CT(p)$, but with $\{\psi(x),\psi(y)\} \neq \{u,v\}$ for all $\psi \in \CT(p)$. But then $p(u)=p(\phi(x)) = p(x)$ and $p(v) = p(\phi'(y)) = p(y)$. Since $p$ is normal, there exists $\zeta \in \CT(p)$ such that $\zeta(x)=u$. The (length-1) walks $(\zeta(x),\zeta(y))$ and $(u,v)$ both start at $\zeta(x)=u$ and project to the same walk $(p(x),p(y))$ in $G$. Hence, by the unique walk-lifting property, we have $\zeta(y)=v$, so $\{\zeta(x),\zeta(y)\}=\{u,v\}$, a contradiction. Hence, $F/\CT(p)$ is a simple graph.

Write $\Gamma: = \CT(p)$. Define a map
$$\Psi:F/\Gamma \to G;\quad \Orb_{\Gamma}(x) \mapsto p(x).$$
We claim that $\Psi$ is a graph isomorphism. Indeed, it is well-defined since $y \in \Orb(x)$ implies that $\phi(x)=y$ for some $\phi \in \CT(p)$, which implies $p(y) = p(\phi(x)) = p(x)$. It is injective since $p(x)=p(y)$ implies $y=\phi(x)$ for some $\phi \in \CT(p)$ (as $p$ is normal), which implies $y \in \Orb(x)$. It is surjective since $p$ is surjective (by Remark \ref{remark:surjective}). It is a homomorphism since if $\{\Orb(x),\Orb(y)\}\in E(F/\Gamma)$, then there exist $\phi_1,\phi_2 \in \CT(p)$ such that $\{\phi_1(x),\phi_2(y)\} \in E(F)$, so $\{p(x),p(y)\} = \{p(\phi_1(x)),p(\phi_2(y))\} \in E(G)$. Finally, $\Psi^{-1}$ is a homomorphism since if $\{a,b\} \in E(G)$, then there exist $x,y \in V(F)$ such that $\{x,y\} \in E(F)$, $p(x)=a$ and $p(y)=b$; but then $\{\Psi^{-1}(a),\Psi^{-1}(b)\} = \{\Orb(x),\Orb(y)\} \in E(F/\Gamma)$. 
\end{proof}

\subsubsection*{Some background from topology and group theory}

\begin{fact}
The group $\Isom(\mathbb{R}^d)$ of isometries of $d$-dimensional Euclidean space satisfies
\begin{align*} \Isom(\mathbb{R}^d) & = \{t \circ \sigma:\ t \in T(\mathbb{R}^d),\ \sigma \in O(d)\}\\
& = \{\sigma \circ t:\ t \in T(\mathbb{R}^d),\ \sigma \in O(d)\}\\
& = T(\mathbb{R}^d) \rtimes O(d),
\end{align*}
where
$$T(\mathbb{R}^d) := \{x \mapsto x+v:\ v \in \mathbb{R}^d\}$$
denotes the group of all translations in $\mathbb{R}^d$, and $O(d) \leq \GL(\mathbb{R}^d)$ denotes the group of all real orthogonal $d \times d$ matrices.
\end{fact}

\begin{fact}
\label{fact:aut-ld}
For any $d \in \mathbb{N}$, we have
\begin{align*} \Aut(\mathbb{L}^d) & = \{t \circ \sigma:\ t \in T(\mathbb{Z}^d),\ \sigma \in B_d\}\\
& = \{\sigma \circ t:\ t \in T(\mathbb{Z}^d),\ \sigma \in B_d\}\\\
&= T(\mathbb{Z}^d) \rtimes B_d,
\end{align*}
where
$$T(\mathbb{Z}^d) :=  \{x \mapsto x+v:\ v \in \mathbb{Z}^d\}$$
denotes the group of all translations by elements of $\mathbb{Z}^d$, and
$$B_d = \{\sigma \in GL(\mathbb{R}^d):\ \sigma(\{\pm e_i:\ i \in [d]\}) = \{\pm e_i: \ i \in [d]\}\},$$
denotes the {\em $d$-dimensional hyperoctahedral group}, which is the symmetry group of the $d$-dimensional (solid) cube with set of vertices $\{-1,1\}^d$, and can be identified with the permutation group
$$\{\sigma \in \Sym([d] \cup \{-i:\ i \in [d]\}):\ \sigma(-i) = -\sigma(i)\ \forall i\},$$
in the natural way (identifying $e_i$ with $i$ and $-e_i$ with $-i$ for all $i \in [d]$). We therefore have $|B_d| = 2^d d!$.
\end{fact}

\begin{fact}
\label{fact:embedding-isometries}
It follows from Fact 2 (or can easily be checked directly) that every element of $\Aut(\mathbb{L}^d)$ can be uniquely extended to an element of $\Isom(\mathbb{R}^d)$. We can therefore view $\Aut(\mathbb{L}^d)$ as a subgroup of $\Isom(\mathbb{R}^d)$.
\end{fact}

\begin{definition}
If $X$ is a topological space, and $\Gamma$ is a group acting on $X$, the {\em orbit space} $X/ \Gamma$ is the (topological) quotient space $X/ \sim$, where $x \sim y$ iff $y \in \Orb_{\Gamma}(x)$, i.e. iff $x$ and $y$ are in the same $\Gamma$-orbit.
\end{definition}

\begin{definition}
If $X$ is a topological space, a group $\Gamma$ of homeomorphisms of $X$ is said to be {\em discrete} if the relative topology on $\Gamma$ (induced by the compact open topology on the group of all homeomorphisms of $X$) is the discrete topology.
\end{definition}

\begin{definition}
If $X$ is a topological space, and $\Gamma$ is a discrete group of homeomorphisms of $X$, we say that $\Gamma$ acts {\em properly discontinuously} on $X$ if for any $x,y \in X$, there exist open neighbourhoods $U$ of $x$ and $V$ of $y$ such that $|\{\gamma \in \Gamma:\ \gamma(U) \cap V \neq \emptyset\}| < \infty$.
\end{definition}

\begin{fact}
\label{fact:discrete}
\begin{comment}
(See e.g. \cite{charlap} Chapter 1.)
\end{comment}
If $\Gamma \leq \Isom(\mathbb{R}^d)$, then $\Gamma$ is discrete if and only if for any $x \in \mathbb{R}^d$, the orbit $\{\gamma(x):\ \gamma \in \Gamma\}$ is a discrete subset of $\mathbb{R}^d$. Hence, $\Aut(\mathbb{L}^d)$ is a discrete subgroup of $\Isom(\mathbb{R}^d)$.
\end{fact}

\begin{fact}
\label{fact:proper-disc}
If $\Gamma \leq \Isom(\mathbb{R}^d)$ is discrete, then $\Gamma$ acts properly discontinuously on $\mathbb{R}^d$. (Note that it is clear directly from the definition that $\Aut(\mathbb{L}^d)$, and any subgroup thereof, acts properly discontinuously on $\mathbb{R}^d$.)
\end{fact}

\begin{definition}
Let $\Gamma$ be a discrete subgroup of $\Isom(\mathbb{R}^d)$. The {\em translation subgroup} $T_{\Gamma}$ of $\Gamma$ is the subgroup of all translations in $\Gamma$. The {\em lattice of translations} of $\Gamma$ is the lattice $L_{\Gamma} := \{\gamma(0):\ \gamma \in T_{\Gamma}\} \subset \mathbb{R}^d$. We have $L_{\Gamma} \cong \mathbb{Z}^r$ for some $r \in \{0,1,\ldots,d\}$; the integer $r$ is called the {\em rank} of the lattice $L_{\Gamma}$.
\end{definition}

\begin{definition}
\label{definition:crystallographic}
A discrete subgroup $\Gamma \leq \Isom(\mathbb{R}^d)$ is said to be a {\em $d$-dimensional crystallographic group} if its lattice of translations has rank $d$ (or, equivalently, if the orbit space $\mathbb{R}^d/\Gamma$ is compact).
\end{definition}

\begin{definition}
A group $\Gamma$ is said to be {\em torsion-free} if the only element of finite order in $\Gamma$ is the identity.
\end{definition}

\begin{definition}(Following \cite{charlap}.)
\label{definition:bieberbach}
A torsion-free $d$-dimensional crystallographic group is called a {\em $d$-dimensional Bieberbach group}.
\end{definition}

\begin{definition}
If $\Gamma$ is a $d$-dimensional crystallographic group, its {\em point group} $P_{\Gamma}$ is defined by
 $$P_{\Gamma} = \{\sigma \in O(d):\ t \circ \sigma \in \Gamma \textrm{ for some }t \in T(\mathbb{R}^d)\}.$$
 \end{definition}

\begin{fact} (Bieberbach's Theorems.)
\label{fact:bieberbach}
Bieberbach's First Theorem \cite{bieberbach-1911} implies that if $\Gamma$ is a $d$-dimensional crystallographic group, then $P_{\Gamma}$ is finite. It is easy to check that if $\Gamma$ is a $d$-dimensional crystallographic group, then its point group $P_{\Gamma}$ acts faithfully on the lattice $L_{\Gamma}$. Hence, $P_{\Gamma}$ is isomorphic to a finite subgroup of $GL_d(\mathbb{Z})$. The Jordan-Zassenhaus theorem implies that for any (fixed) $d \in \mathbb{N}$, there are only finitely many isomorphism-classes of finite subgroups of $\GL_d(\mathbb{Z})$. It follows that for any $d \in \mathbb{N}$, there are only finitely many possibilities for the isomorphism class of the point-group of a $d$-dimensional crystallographic group. Bieberbach's Third Theorem \cite{bieberbach-1912} says more: for any $d \in \mathbb{N}$, there are only finitely many possibilities for the isomorphism class\footnote{Meaning, as usual, an isomorphism class of abstract groups.} of a $d$-dimensional crystallographic group. Bieberbach's Second Theorem \cite{bieberbach-1912} states that if $\Gamma$ and $\Gamma'$ are $d$-dimensional crystallographic groups, and $\Phi:\Gamma \to \Gamma'$ is an isomorphism, then there exists an affine transformation $\alpha$ of $\mathbb{R}^d$ such that $\Phi(\gamma) = \alpha^{-1} \gamma \alpha$ for all $\gamma \in \Gamma$. Hence, two $d$-dimensional crystallographic groups are isomorphic if and only if they are conjugate in $\Aff(\mathbb{R}^d)$, the group of all affine transformations of $\mathbb{R}^d$. It follows that for any fixed $d \in \mathbb{N}$, there are only a finite number ($f(d)$, say) of possibilities for the affine-conjugacy class of a $d$-dimensional crystallographic group.
\end{fact}

\begin{definition}($d$-dimensional topological manifold.)

Let $d \in \mathbb{N}$. A Hausdorff topological space $X$ is said to be a {\em $d$-dimensional topological manifold} if for every $x \in X$, there exists an open neighbourhood of $x$ which is homeomorphic to an open subset of $\mathbb{R}^d$. (Note that we do not regard a `manifold with boundary' as a manifold.)
\end{definition}

\begin{definition}($d$-dimensional topological orbifold, following \cite{lectures-on-orbifolds}.)
\label{defn:orbifold}
\label{page:orbifold-definition}

Let $d \in \mathbb{N}$ be fixed. Let $X$ be a Hausdorff topological space. An {\em orbifold chart} on $X$ is a 4-tuple $(V,G,U,\pi)$, where
\begin{itemize}
\item $V$ is an open subset of $\mathbb{R}^d$;
\item $U$ is an open subset of $X$;
\item $G$ is a finite group of homeomorphisms of $V$;
\item $\pi = \phi \circ q$, where $q: V \to V/G$ is the orbit map (i.e. the map taking $v \in V$ to its orbit), and $\phi:V/G \to U$ is a homeomorphism.
\end{itemize}
We say that two orbifold charts $(V_1,G_1,U_1,\pi_1),\ (V_2,G_2,U_2,\pi_2)$ on $X$ are {\em compatible} if for any $v_1 \in V_1,\ v_2 \in V_2$ with $\pi_1(v_1) = \pi_2(v_2)$, there exist open neighbourhoods $W_i$ of $v_i$ in $V_i$ (for $i=1,2$), and a homeomorphism $h:W_2 \to W_1$, such that $\pi_2 | W_2 = (\pi_1 |W_1) \circ h$.

An {\em atlas of orbifold charts on $X$} is a collection $\{(V_i,G_i,U_i,\pi_i):\ i \in I\}$ of pairwise compatible orbifold charts on $X$ such that $\{U_i:\ i \in I\}$ is a cover of $X$. A {\em $d$-dimensional topological orbifold} is a pair $(X,\mathcal{A})$, where $X$ is a topological space, and $\mathcal{A}$ is an atlas of orbifold charts on $X$. (Abusing terminology slightly, if $(X,\mathcal{A})$ is a topological orbifold, we will sometimes refer to the underlying topological space $X$ as a topological orbifold.)
\end{definition}

Note that, for simplicity, all orbifolds (and manifolds) in this paper will be viewed only as topological ones. An `orbifold' (resp. `manifold') will therefore always mean a topological orbifold (resp. manifold).

\begin{remark}
Informally, a $d$-dimensional topological orbifold is a topological space, together with a collection of charts which model it locally using quotients of open subsets of $\mathbb{R}^d$ under the actions of finite groups (rather than simply using open subsets of $\mathbb{R}^d$, as in the definition of a manifold). Note that a $d$-dimensional manifold is precisely a $d$-dimensional orbifold where we can take each finite group $G_i$ in Definition \ref{defn:orbifold} to be the trivial group.
\end{remark}

\begin{example}
The orbit space $\mathbb{R}^2/\langle (x_1,x_2) \mapsto (x_1,-x_2) \rangle$ (which is homeomorphic to the closed upper half-plane) can be given the structure of a 2-dimensional orbifold. More generally, any `manifold with boundary' can be given the structure of an orbifold. Even more generally, if $M$ is a manifold, and $\Gamma$ is a finite group of homeomorphisms of $M$, then the orbit space $M/\Gamma$ can be given the structure of an orbifold.
\end{example}

\begin{fact}
\label{fact:proper-orbifold}(See \cite{orbifolds}, Proposition 13.2.1.)
If $\Gamma$ is a discrete group of homeomorphisms of a $d$-dimensional topological manifold $M$, and $\Gamma$ acts properly discontinuously on $M$, then the orbit space $M/\Gamma$ can be given the structure of a $d$-dimensional topological orbifold. This follows from the facts that for each $x \in M$, $\Stab_{\Gamma}(x)$ is finite, and that for any open neighbourhood $W$ of $x$, there exists an open neighbourhood $U_x$ of $x$ such that $U_x \subset W$, $\gamma(U_x) = U_x$ for all $\gamma \in \Stab_{\Gamma}(x)$ and $\gamma(U_x) \cap U_x = \emptyset$ for all $\gamma \in \Gamma \setminus \Stab_{\Gamma}(x)$; for each $x \in M$, we can therefore take a chart at $x$ where the finite group of homeomorphisms $G_x$ is (isomorphic to) $\Stab_{\Gamma}(x)$. If, in addition, $\Gamma$ is torsion-free, then $\Stab_{\Gamma}(x)$ is trivial for all $x$, so $M/\Gamma$ is a $d$-dimensional topological manifold.
\end{fact}

\begin{fact}
It follows from Facts \ref{fact:proper-disc} and \ref{fact:proper-orbifold} that if $\Gamma \leq \Isom(\mathbb{R}^d)$ is discrete, then $\mathbb{R}^d/\Gamma$ is a $d$-dimensional orbifold, and if in addition, $\Gamma$ is torsion-free, then $\mathbb{R}^d/\Gamma$ is a $d$-dimensional manifold. Therefore, if $\Gamma$ is a $d$-dimensional crystallographic group, then $\mathbb{R}^d/\Gamma$ is a compact $d$-dimensional orbifold, and if $\Gamma$ is a $d$-dimensional Bieberbach group, then $\mathbb{R}^d/\Gamma$ is a compact $d$-dimensional manifold. Since there are at most $f(d)$ possibilities for the affine-conjugacy class of a $d$-dimensional crystallographic group, the orbit space $\mathbb{R}^d/\Gamma$ is homeomorphic to one of at most $f(d)$ topological spaces.
\end{fact}

\subsubsection*{Some background on topological coverings}
In Section 4 (alone), we will need to consider general topological coverings. For more detail, the reader may consult e.g. \cite{hatcher}.

\begin{definition}
Let $X$ and $Y$ be topological spaces. We say that a continuous map $p:X \to Y$ is a {\em covering map} if for every $y \in Y$, there exists an open neighbourhood $U_y$ of $y$ such that $p^{-1}(U_y)$ is a disjoint union of open sets in $X$, each of which is mapped homeomorphically onto $U_y$ by $p$. The space $X$, or more formally, the triple $(X,Y,p)$, is called a {\em covering space} of $Y$.
\end{definition}

\begin{remark}
\label{remark:subspace-covering}
Note that if $(X,Y,p)$ is a covering space, and $Y'$ is a subspace of $Y$, then the restriction $(p^{-1}(Y'),Y',p|p^{-1}(Y'))$ is also a covering space.
\end{remark}

\begin{definition}
If $(X,Y,p)$ is a covering space, $Z$ is a topological space, and $f:Z \to Y$ is a map, then a {\em $p$-lift} of $f$ is a map $g:Z \to X$ such that $p \circ g = f$. (When the map $p$ is understood, we will sometimes write {\em lift} in place of {\em $p$-lift}.)
\end{definition}

\begin{definition}
If $(X,Y,p)$ is a covering space, a {\em covering transformation} of $(X,Y,p)$ is a homeomorphism $\phi:X \to X$ such that $p \circ \phi = p$.
\end{definition}

\begin{definition}
We say a covering space $(X,Y,p)$ is {\em normal} if for every $x,x' \in X$ such that $p(x) = p(x')$, there exists a covering transformation $\phi$ of $(X,Y,p)$ such that $\phi(x)=x'$.
\end{definition}

\begin{definition}
Two covering spaces $(X_1,Y,p_1)$ and $(X_2,Y,p_2)$ are said to be {\em isomorphic} if there exists a homeomorphism $\phi:X_1 \to X_2$ such that $p_1 = p_2 \circ \phi$.
\end{definition}

\begin{fact}(Universal covering spaces.)

If $(X,Y,p)$ is a covering space with $X$ simply connected, then $(X,Y,p)$ is called a {\em universal covering space} of $Y$. It is unique in the sense that if $(X',Y,p)$ is another covering space of $Y$ with $X'$ simply connected, then $(X,Y,p)$ and $(X',Y,p)$ are isomorphic, so it is often called `the' universal covering space of $Y$. It is also a normal covering space. Every connected, locally path-connected and semi-locally simply connected topological space has a universal covering space. If a topological space $Y$ is simply connected, then $(Y,Y,\textrm{Id})$ is a universal covering space for $Y$ --- that is, $Y$ is its own universal cover.
\end{fact}

\begin{fact}(Unique homotopy-lifting property.)
\label{fact:homotopy-lifting}

Let $(X,Y,p)$ be a covering space, let $Z$ be a topological space, and let $F:Z \times [0,1] \to Y$ be a homotopy from $Z$ to $Y$. Define $f:Z \to Y;\ z \mapsto F(z,0)$. If $g:Z \to X$ is a lift of $f$, then there is a unique homotopy $G:Z \times [0,1] \to X$ such that $G$ is a lift of $F$, and $G(z,0) = g(z)$ for all $z \in Z$.
\end{fact}

A special case of this (taking $Z$ to be a point) is the following.

\begin{fact}(Unique path-lifting property.)

Let $(X,Y,p)$ be a covering space, let $y_0 \in Y$, and let $\gamma$ be a path in $Y$ starting at $y_0$, i.e. $\gamma:[0,1] \to Y$ is a continuous map with $\gamma(0)=y_0$. Then for any $x_0 \in X$ with $p(x_0)=y_0$, there is a unique lift of $\gamma$ starting at $x_0$.
\end{fact}

\subsubsection*{Some background from the geometry of surfaces}
The following definitions and facts will also be needed in Section 4 (alone).

\begin{definition} A {\em(topological) surface} is a 2-dimensional topological manifold. (Note that we do not regard a `surface with boundary' as a surface.)
\end{definition}

For simplicity, all surfaces in this paper will be viewed only as topological ones.

\begin{definition} A surface is said to be {\em non-orientable} if it contains a subspace homeomorphic to the M\"obius strip, and {\em orientable} otherwise.
\end{definition}

\begin{fact}(The Classification Theorem for Surfaces.)
\label{fact:classification}

The {\em classification theorem for surfaces} states that any orientable connected compact surface is homeomorphic to a sphere with $g$ handles, for some unique $g \in \mathbb{N} \cup \{0\}$ (in which case it is said to have genus $g$), and that any non-orientable connected compact surface is homeomorphic to a sphere with $k$ cross-caps, for some unique $k \in \mathbb{N}$ (in which case it is said to have genus $k$).
\end{fact}

\begin{fact}(Universal covering surfaces.)
\label{fact:covering-surface}

Every connected compact surface $S$ has a universal covering space, which is also a surface; it is called the {\em universal covering surface of $S$}. Since this surface is simply connected, it is (homeomorphic to) either the sphere or the plane $\mathbb{R}^2$. The sphere and the projective plane both have the sphere as their universal cover; every other connected compact surface has the plane as its universal cover. In particular, both the torus and the Klein bottle have the plane as their universal cover.
\end{fact}

\begin{definition} Let $S$ be a surface. Let $S^1$ denote the unit circle. A {\em simple arc} in $S$ is a continuous injective map $\gamma:[0,1] \to S$. A {\em simple, closed curve} in $S$ is a continuous injective map $\delta:S^1\to S$. A {\em loop} in $S$ is a continuous map $\delta:S^1 \to S$.
\end{definition}

\begin{definition}(Embedded graph.)

Let $S$ be a surface. We say a (simple) graph $G$ is {\em embedded} on $S$ if:
\begin{itemize}
\item the vertices of $G$ are points of $S$.
\item the edges of $G$ are simple arcs in $S$.
\item if $\gamma:[0,1] \to S$ is an edge of $G$, we have $\gamma(0),\gamma(1) \in V(G)$ and $\gamma(x) \notin V(G)$ for all $x \in (0,1)$. In other words, for any edge of $G$, both its endpoints are vertices of $G$, but none of its interior points are vertices of $G$.
\item any two distinct edges of $G$ have at most one endpoint and no interior point in common.
\end{itemize}
\end{definition}

\begin{definition}
If $G$ is a graph embedded on a surface $S$, we let $[G]$ denote the {\em point-set} of $G$, that is, the subset of $S$ consisting of the union of the vertices and the edges of $G$. A {\em face} of $G$ is a path-component of $S \setminus [G]$. A {\em closed face} is the (topological) closure of a face of $G$. (It will sometimes be more convenient to work with closed faces, rather than faces.)
\end{definition}

\begin{definition}
If $S$ is a surface, $G$ is a graph embedded on $S$, and $x \in S$, we say that $x$ is a {\em vertex accumulation point} for $G$ if there is an infinite sequence $(v_n)$ of distinct vertices of $G$ such that $v_n \to x$ as $n \to \infty$.
\end{definition}

\begin{definition}
If $G$ is a simple graph embedded on a connected surface $S$, with no vertex-accumulation point, then $G$ is said to be a {\em subdivision} of $S$ if every face of $G$ is homeomorphic to an open disc in $\mathbb{R}^2$.
\end{definition}

\begin{definition}
The {\em Euler characteristic} $\chi(S)$ of a connected compact surface $S$ is defined by
$$\chi(S) = v(G) - e(G) +f(G),$$
where $G$ is any subdivision of $S$ with $|v(G)| < \infty$, and $v(G),e(G),f(G)$ are the numbers of vertices, edges and faces of $G$, respectively. (Remarkably, this quantity is independent of the subdivision $G$.)
\end{definition}

\begin{fact} If $S$ is an orientable surface of genus $g$, then $\chi(S) = 2-2g$, and if $S$ is a non-orientable surface of genus $k$, then $\chi(S) = 2-k$. Hence, by the classification theorem for surfaces, a connected compact surface is determined (up to homeomorphism) by its Euler characteristic, plus whether or not it is orientable.
\end{fact}

\begin{definition}
If $S$ is a connected surface, and $G$ is a subdivision of $S$, we say that $G$ is a {\em quadrangulation} of $S$ if the boundary of every face of $G$ is a 4-cycle of $G$. We call these cycles the {\em face-cycles} of $G$.
\end{definition}

\begin{definition}
If $S$ is a connected surface, and $G, H$ are two quadrangulations of $S$, we say that $H$ is {\em isomorphic to $G$ (as a quadrangulation of $S$)} if there exists a graph isomorphism $\phi:G \to H$ such that
$$\phi(v_1) \phi(v_2) \phi(v_3) \phi(v_4) \phi(v_1)$$
is a face-cycle of $H$ if and only if
$$v_1 v_2 v_3 v_4 v_1$$
is a face-cycle of $G$.
\end{definition}

\begin{remark}(Lifting an embedded graph.)
\label{remark:covering-connection}

If $G$ is a finite graph embedded on a connected surface $S$, and $(X,S,p)$ is a covering space of $S$ with $X$ connected, then $X$ is a surface, $p^{-1}(V(G))$ is a discrete set of points in $X$, and by the unique path-lifting property, for every edge $e$ of $G$, $p^{-1}(e)$ is a disjoint union of simple arcs in $X$ (each such arc is a lift of $e$). We define the {\em lift of $G$ to $X$} to be the graph embedded on $X$, whose vertex-set is $p^{-1}(V(G))$, and whose edges are all the simple arcs which are lifts of edges of $G$. We write $p^{-1}(G)$ for the lift of $G$. It is easy to check that the map $p|V(p^{-1}(G)):V(p^{-1}(G)) \to V(G)$ is a covering of $G$ by $p^{-1}(G)$, in the graph sense.\end{remark}

\begin{fact}(Homotopy-invariance of winding numbers.)
\label{fact:winding-numbers}
If $\delta$ is a loop in $\mathbb{R}^2 \setminus \{x\}$, let $n(\delta,x)$ denote the winding number of $\delta$ around $x$. If $U \subset \mathbb{R}^2$ is a simply-connected open set containing $x$, and $\delta$ is a loop in $U \setminus \{x\}$, then $n(\delta,x) = 0$ if and only if $\delta$ is homotopic to a constant loop in $U \setminus \{x\}$. More generally, if $\delta$ and $\delta'$ are loops in $U \setminus \{x\}$, then $n(\delta,x) = n(\delta',x)$ if and only if $\delta$ and $\delta'$ are homotopic in $U \setminus \{x\}$.
\end{fact}

\begin{comment}
see Elias Wegert, Visual Complex Functions.
\begin{definition}
Let $\Gamma$ be a group acting on a set $S$. We say that $\Gamma$ acts {\em freely} on $S$ if $\gamma(x) \neq x$ for all $\gamma \in \Gamma \setminus \{\Id\}$ and all $x \in X$.
\end{definition}

\begin{fact}
If $\Gamma$ is a torsion-free discrete group of homeomorphisms of a topological space $X$, acting properly discontinuously on $X$, then $\Gamma$ acts freely on $X$
\end{fact}

\begin{fact}
If $\Gamma$ is a group acting freely and properly discontinuously on a manifold $M$, then the orbit space $M/\Gamma$ is also a manifold (with the natural manifold structure).
\end{fact}
\end{comment}

\section{Constructive proofs of structure theorems}
Our main aim in this section is to prove Theorems \ref{thm:cover-2} and \ref{thm:cover-d} by direct constructions of the appropriate normal covering maps. First, we need some simple observations.

\begin{observation}
\label{obs:odd-cycles}
Notice that for any $d,r \in \mathbb{N}$, we have
$$\Link_r^{-}(0,\mathbb{L}^d) = \Link_r(0,\mathbb{L}^d).$$
Hence, a graph $G$ is $r$-locally $\mathbb{L}^d$ if and only if it is weakly $r$-locally-$\mathbb{L}^d$ and has no odd cycle of length $2r+1$.
\end{observation}

\begin{observation}
\label{obs:bijective-homomorphism}
It is easy to see that a graph $G$ is weakly $r$-locally $\mathbb{L}^d$ if and only if for every $v \in V(G)$, there exists a bijective graph homomorphism $\psi:\Link_r(0,\mathbb{L}^d) \to \Link_r(v,G)$ such that $\psi(0)=v$. 
\end{observation}

\begin{observation}
\label{observation:opposite-2}
Let $G$ be a graph which is weakly $2$-locally $\mathbb{L}^2$. Then for each vertex $u \in V(G)$, there is a partition of $\Gamma(u)$ into two pairs,
\begin{equation}\label{eq:2-pairs}\{\{a^{(1)}_1,a^{(1)}_{2}\},\ \{a^{(2)}_1,a^{(2)}_{2}\}\}\end{equation}
such that for each $i \in \{1,2\}$, $a_1^{(i)}$ and $a_2^{(i)}$ have $u$ as their only common neighbour, and for each $(k,l) \in [2]^2$, there are exactly two common neighbours of $a^{(1)}_k$ and $a^{(2)}_l$, namely $u$ and one other vertex $c_{(k,l)}$, with the $4$ vertices
$$(c_{(k,l)}:\ (k,l) \in [2]^2)$$
being distinct. Further, the partition (\ref{eq:2-pairs}) is the unique partition with these properties. For each $i \in \{1,2\}$, we say that the two vertices $a^{(i)}_1$ and $a^{(i)}_2$ are `opposite one another across $u$'.
\end{observation}

\begin{observation}
\label{observation:opposite}
Let $d \geq 2$ be an integer. Let $G$ be a graph which is weakly $2$-locally $\mathbb{L}^d$. Then $G$ is $(2d)$-regular, and for each vertex $u \in V(G)$, the set of neighbours of $u$ can be partitioned into $d$ pairs
\begin{equation}\label{eq:d-pairs}\{\{a^{(i)}_1,a^{(i)}_{2}\}:\ i \in [d]\}\end{equation}
such that for all $i \in [d]$, $a_1^{(i)}$ and $a_2^{(i)}$ have $u$ as their only common neighbour, and for each pair $1 \leq i < j \leq d$ and each $(k,l) \in [2]^2$, there are exactly two common neighbours of $a^{(i)}_k$ and $a^{(j)}_l$, namely $u$ and one other vertex $c_{\{i,j\},(k,l)}$, with the $4{d \choose 2}$ vertices
$$(c_{\{i,j\},(k,l)}:\ \{i,j\} \in [n]^{(2)},\ (k,l) \in [2]^2)$$
being distinct. Further, the partition (\ref{eq:d-pairs}) is the unique partition with these properties. For each $i \in [d]$, we say that the two vertices $a^{(i)}_1$ and $a^{(i)}_2$ are `opposite one another across $u$'.
\end{observation}

\begin{remark}
\label{remark:3locally}
Suppose that $G$ is weakly 2-locally $\mathbb{L}^d$ for some integer $d \geq 2$. Suppose $a_1$ and $a_2$ are opposite one another across $u$, and $b \in \Gamma(u) \setminus \{a_1,a_2\}$. Then $a_1$ and $b$ have exactly two common neighbours, $u$ and $c_1$ (say). Similarly, $a_2$ and $b$ have exactly two common neighbours, $u$ and $c_2$ (say). If, in addition, $G$ is weakly $3$-locally $\mathbb{L}^d$, then $c_1$ and $c_2$ must be opposite one another across $b$, since $b$ is their only common neighbour. (Example \ref{example:Ld} shows that for each $d \geq 3$, this need not be true if $G$ is merely $2$-locally-$\mathbb{L}^d$.)
\end{remark}

We will also need the following.

\begin{lemma}
\label{lemma:condition}
Let $d \geq 2$ be an integer. Suppose $G$ is weakly $2$-locally $\mathbb{L}^d$. Suppose further that $p:V(\mathbb{L}^d) \to V(G)$ is a covering map from $\mathbb{L}^d$ to $G$. Then for every $x \in V(\mathbb{L}^d)$ and every $i \in [d]$, $p(x+e_i)$ is opposite $p(x-e_i)$ across $p(x)$.
\end{lemma}
\begin{proof}
Without loss of generality, we may assume that $x=0$, and $i=1$. Suppose for a contradiction that $p(e_1)$ is not opposite $p(-e_1)$ across $p(0)$. Then there exists $s \in \{\pm 1\}$ and $j \neq 1$ such that $p(se_j)$ is opposite $p(e_1)$ across $p(0)$, i.e. $p(0)$ is the unique common neighbour of $p(e_1)$ and $p(se_j)$. Since $p$ is a graph homomorphism, and $e_1+se_j$ is a common neighbour of $e_1$ and $se_j$, we must have $p(se_j+e_1) = p(0)$. But this contradicts the fact that $p$ is injective on $N(e_1)$, proving the lemma.
\end{proof}

Our main tool for proving Theorem \ref{thm:cover-2} will be the following claim.
\begin{claim}
\label{claim:exist-unique2}
If $S \subset \mathbb{Z}^2$, let $N(S) := N_{\mathbb{L}^2}(S)$ denote the neighbourhood of $S$ in the graph $\mathbb{L}^2$. Let $G$ be a connected graph which is weakly $2$-locally $\mathbb{L}^2$. Let $p_0:\{0,e_1,-e_1,e_2,-e_2\} \to V(G)$ be an injection such that $p_0(e_1)$ and $p_0(-e_1)$ are opposite one another across $p_0(0)$, and such that $p_0(e_2)$ and $p_0(-e_2)$ are opposite one another across $p_0(0)$. Let $P$ be a geodesic (in $\mathbb{L}^2$) from $0$ to some other point $x \in \mathbb{Z}^2$. Then there is a unique way of extending $p_0$ to a map $p: N(P) \to V(G)$ such that the restriction $p\,|\,N(w) \cap N(P)$ is an injective graph homomorphism from $\mathbb{L}^2[N(w) \cap N(P)]$ to $G$, for all $w \in N(P)$.
\end{claim}
\begin{proof}[Proof of Claim \ref{claim:exist-unique2}.]
Let $P = (x_0, x_1 , \ldots, x_l)$, where $x_0 = 0$ and $x_l = x$. For each $k \in [l]$, let $P_k$ denote the sub-path of $P$ between $0$ and $x_k$. Without loss of generality, we may assume that $x$ lies in the positive quadrant, i.e. both of its coordinates are non-negative. Then, since $(x_i)_{i=0}^{l}$ is a geodesic, each $x_i$ also lies in the positive quadrant, and furthermore $x_i - x_{i-1} \in \{e_1,e_2\}$ for all $i \in [l]$.

We will prove that the claim holds for $P_k$, for all $k \leq l$, by induction on $k$. By definition, it holds for $P_0$. Assume that it holds for $P_{k-1}$, where $k \geq 1$; we will prove that it holds for $P_k$. Let $p$ be an extension of $p_0$ to $N(P_{k-1})$, satisfying the conclusion of the claim when $P$ is replaced by $P_{k-1}$; we will show that there is a unique way to extend $p$ to $N(P_k)$ in such a way that the conclusion of the claim holds when $P$ is replaced by $P_k$.

Note that $x_k - x_{k-1} \in \{e_1,e_2\}$. Without loss of generality, we may assume that $x_k - x_{k-1} = e_1$. For brevity, let us write $v:=x_{k-1}$. We split into two cases:
\begin{description}
\item[case 1:] $k > 1$ and $x_{k-1} - x_{k-2} =e_2$;
\item[case 2:] $k=1$, or $x_{k-1} - x_{k-2} =e_1$.
\end{description}
First assume we are in case 1. We assert that $p(v-e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$. To see this, note that we have already defined $p$ at $v$, $v+e_1$, $v - e_1$, and $v+e_2$, $v -e_2$, $v + e_1-e_2$, and $v - e_1-e_2$. Observe that $p(v-e_2)$ and $p(v - e_1)$ have two common neighbours (namely, $p(v)$ and $p(v-e_1-e_2)$; these are distinct, as $v$ and $v-e_1-e_2$ are both neighbours of $v - e_2$). Moreover, $p(v-e_2)$ and $p(v+e_1)$ have two common neighbours (namely, $p(v)$ and $p(v+e_1-e_2)$; these are distinct, as $v$ and $v+e_1-e_2$ are both neighbours of $v-e_2$). It follows that $p(v - e_2)$ and $p(v+e_2)$ have $p(v)$ as their only common neighbour, i.e. $p(v - e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$, as asserted.

It follows from this assertion that $p(v+e_2)$ and $p(v+e_1)$ must have two common neighbours, $p(v)$ and one other vertex. We must define $p(v+e_1+e_2)$ to be this other vertex. To check that $p$ is injective on neighbourhoods (so far), we must check that $p(v+e_1+e_2) \neq p(v+e_1-e_2)$. Suppose for a contradiction that $p(v+e_1+e_2) = p(v+e_1-e_2)$. Then $p(v - e_2)$ and $p(v+e_2)$ have two common neighbours, namely $p(v)$ and $p(v+e_1+e_2)$ (these are distinct, by our definition of $p(v+e_1+e_2)$) --- but this contradicts the fact that $p(v - e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$.

It remains to define $p$ on $v+2e_1$. We have already defined $p$ on the other three neighbours of $v+e_1$, in such a way that the images are distinct neighbours of $p(v+e_1)$; there is just one more neighbour of $p(v+e_1)$, and we must define $p(v+2e_1)$ to be this vertex. By construction, $p|N(w) \cap N(P_k)$ is an injective graph homomorphism from $\mathbb{L}^2[N(w) \cap N(P_k)]$ into $G$ for all $w \in \{v+e_1,v+e_1+e_2\}$, and so for all $w \in N(P_k)$. Moreover, $p$ is the unique such map. This completes the inductive step in case 1.

Now suppose we are in case 2. We assert, as before, that $p(v - e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$. If $k=1$, then this is immediate. Assume therefore that $k \geq 2$. Note that we have already defined $p$ at $v$, $v-e_1$, $v + e_2$, and $v-e_2$, $v - e_1+e_2$, and $v -e_1-e_2$. Note that $p(v-e_1)$ and $p(v - e_2)$ have two common neighbours (namely, $p(v)$ and $p(v-e_1-e_2)$; these are distinct, as $v$ and $v-e_1-e_2$ are both neighbours of $v - e_2$). Moreover, $p(v-e_1)$ and $p(v+e_2)$ have two common neighbours (namely, $p(v)$ and $p(v-e_1+e_2)$; these are distinct, as $v$ and $v-e_1+e_2$ are both neighbours of $v-e_1$). It follows that $p(v - e_2)$ and $p(v+e_2)$ have $p(v)$ as their only common neighbour, i.e. $p(v - e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$, as asserted.

It follows from this assertion that $p(v+e_2)$ and $p(v+e_1)$ must have two common neighbours, $p(v)$ and one other vertex. We must define $p(v+e_1+e_2)$ to be this other vertex. Moreover, it follows that $p(v-e_2)$ and $p(v+e_1)$ must have two common neighbours, $p(v)$ and one other vertex. We must define $p(v+e_1-e_2)$ to be this other vertex. To check that $p$ is injective on neighbourhoods (so far), we must check that $p(v+e_1+e_2) \neq p(v+e_1-e_2)$. Suppose for a contradiction that $p(v+e_1+e_2) = p(v+e_1-e_2)$. Then $p(v - e_2)$ and $p(v+e_2)$ have two common neighbours, namely $p(v)$ and $p(v+e_1+e_2)$ (these are distinct, by our definition of $p(v+e_1+e_2)$) --- but this contradicts the fact that $p(v - e_2)$ and $p(v+e_2)$ are opposite one another across $p(v)$.

It remains to define $p$ on $v+2e_1$. We have already defined $p$ on the other three neighbours of $v+e_1$, in such a way that the images are distinct neighbours of $p(v+e_1)$; there is just one more neighbour of $p(v+e_1)$, and we must define $p(v+2e_1)$ to be this vertex. By construction, $p|N(w) \cap N(P_k)$ is an injective graph homomorphism from $\mathbb{L}^2[N(w) \cap N(P_k)]$ into $G$ for all $w \in \{v+e_1,v+e_1+e_2,v+e_1-e_2\}$, and so for all $w \in N(P_k)$. Moreover, $p$ is the unique such map. This completes the inductive step in case 2, completing the proof of Claim \ref{claim:exist-unique2}.
\end{proof}

We are now ready to prove Theorem \ref{thm:cover-2}.

\begin{proof}[Proof of Theorem \ref{thm:cover-2}.]
Let $G$ be a connected graph which is weakly $2$-locally $\mathbb{L}^2$. Choose any vertex $v_0 \in V(G)$ and define $p_0(0) = v_0$. By Observation \ref{observation:opposite-2}, there is a partition of $\Gamma(v_0)$ into two pairs
$$\{a^{(1)}_1,a^{(1)}_{2}\},\ \{a^{(2)}_1,a^{(2)}_{2}\}$$
such that $a^{(i)}_1$ and $a^{(i)}_2$ are opposite one another across $v_0$, for each $i \in \{1,2\}$. Define $p_0(e_1) = a^{(1)}_1$, $p_0(-e_1) = a^{(1)}_2$, $p_0(e_2) = a^{(2)}_1$, and $p_0(-e_2) = a^{(2)}_2$. Now we extend $p_0$ to a map $q$ on all of $\mathbb{Z}^2$, as follows. For each $x \in \mathbb{Z}^2$, choose a geodesic $P$ from $0$ to $x$. Since $p_0$ satisfies the hypothesis of Claim \ref{claim:exist-unique2}, we can extend $p_0$ to a map $p_{P}$ from $N(P)$ to $V(G)$ with the property in the conclusion of Claim \ref{claim:exist-unique2}. We define $q(x)=p_{P}(x)$.

Our next aim is to prove:
\begin{equation} \label{eq:well-defined} p_{P}(x) \textrm{ is independent of the choice of geodesic }P \textrm{ from }0 \textrm{ to } x.\end{equation}

To prove (\ref{eq:well-defined}), we may assume without loss of generality that $x$ is in the positive quadrant. Observe that for any two geodesics $P,P'$ from $0$ to $x$, we can get from $P$ to $P'$ by a sequence of {\em elementary switches}, meaning operations which replace some sub-path $(v,v+e_1,v+e_1+e_2)$ by the sub-path $(v,v+e_2,v+e_1+e_2)$, or vice versa. Hence, it suffices to show that if $P$ and $P'$ differ from one another by an elementary switch, then we have $p_{P}(x) = p_{P'}(x)$. Suppose then that $P = (v_0,v_1,\ldots,v_k,v_k+e_1,v_k+e_1+e_2,v_{k+3},\ldots, v_l)$ and $P' = (v_0,v_1,\ldots,v_k,v_k+e_2,v_k+e_1+e_2,v_{k+3},\ldots, v_l)$, where $v_0 = 0$ and $v_l = x$. For brevity, let us define $p := p_{P}$ and $p' := p_{P'}$, and let us write $v = v_k$. Then $p(v) = p'(v)$, $p(v+e_2) = p'(v+e_2)$ and $p(v+e_1) = p'(v+e_1)$, since $P'_k = P_k$ and $p$ is uniquely determined on $N(P_k)$ (and $p'$ on $N(P'_k)$). Hence, $p(v+e_1+e_2) = p'(v+e_1+e_2)$. If $x = v+e_1+e_2$, then we are done, so we may assume henceforth that $l \geq k+3$. We claim that $p$ and $p'$ agree on the remaining two neighbours of $v+e_1+e_2$, namely $v+2e_1+e_2$ and $v+e_1+2e_2$. There are two cases:
\begin{description}
\item[case 1:] $v_{k+3} = v_{k+2}+e_1 (= v+2e_1+e_2)$
\item[case 2:] $v_{k+3} = v_{k+2}+e_2 (= v+e_1+2e_2)$.
\end{description}
In case 1, note that $p(v+e_1) = p'(v+e_1)$ has two neighbours in common with $p(v+e_2) = p'(v+e_2)$ and also two neighbours in common with $p(v+2e_1+e_2)$, and two neighbours in common with $p'(v+2e_1+e_2)$. Hence, we must have $p'(v+2e_1+e_2) = p(v+2e_1+e_2)$, and therefore $p'(v+e_1+2e_2) = p(v+e_1+2e_2)$.

In case 2, note that $p(v+e_2) = p'(v+e_2)$ has two neighbours in common with $p(v+e_1) = p'(v+e_1)$ and also two neighbours in common with $p(v+e_1+2e_2)$, and two neighbours in common with $p'(v+e_1+2e_2)$. Hence, we must have $p'(v+e_1+2e_2) = p(v+e_1+2e_2)$, and therefore $p'(v+2e_1+e_2) = p(v+2e_1+e_2)$.

In both cases, we have $p=p'$ on $N(v_{k+2})$. By the uniqueness part of Claim \ref{claim:exist-unique2} (applied with $v_{k+2}$ in place of $0$), it follows that $p = p'$ on $(v_{k+2},v_{k+3},\ldots,v_l)$, so in particular $p(x) = p'(x)$, proving (\ref{eq:well-defined}).

By (\ref{eq:well-defined}) and the property in Claim \ref{claim:exist-unique2}, $q|N(w)$ is an injective graph homomorphism from $\mathbb{L}^2[N(w)]$ into $G$, for all $w \in \mathbb{Z}^2$; this says precisely that $q$ is a covering map from $\mathbb{L}^2$ to $G$. Moreover, by the uniqueness part of Claim \ref{claim:exist-unique2}, we have a `strong uniqueness property':
\begin{equation}
\label{eq:strong-uniqueness-2} 
q \textrm{ is the unique covering map from }\mathbb{L}^2 \textrm{ to } G \textrm{ agreeing with }p_0 \textrm{ on }N(0).\end{equation}
This actually implies that $q$ is a normal covering map. To see this, it suffices to show that the group of covering transformations of $q$ is transitive on the fibre $q^{-1}(0)$. So let $v \in \mathbb{Z}^2 \setminus \{0\}$ with $q(v) = q(0)$. By Lemma \ref{lemma:condition}, $q(e_1)$ and $q(-e_1)$ are opposite one another across $q(0)$, and $q(v+e_1)$ and $q(v-e_1)$ are opposite one another across $q(v)=q(0)$. Hence, we have
\begin{align*} & \{\{q(v+e_1),q(v-e_1)\},\{q(v+e_2),q(v-e_2)\}\}\\
= & \{\{q(e_1),q(-e_1)\},\{q(e_2),q(-e_2)\}\}.\end{align*}
Since $\Aut(\mathbb{L}^2) = T(\mathbb{Z}^2) \rtimes B_2$, and the elements of $B_2$ correspond precisely to the permutations of $\{e_1,-e_1,e_2,-e_2\}$ which preserve the partition
$$\{\{e_1,-e_1\},\{e_2,-e_2\}\}$$
(see Fact \ref{fact:aut-ld}), we may choose $\alpha \in \Aut(\mathbb{L}^2)$ such that $\alpha(0) = v$ and $q(w) = q(\alpha(w))$ for all $w \in \Gamma(0)$. (Take $\alpha = g \circ t_v$, where $t_v$ is translation by $v$ and $g$ is the appropriate element of $B_2$.) 

Observe that $q \circ \alpha$ is a covering map from $\mathbb{L}^2$ to $G$ which agrees with $q$ (and therefore with $p_0$) on $N(0)$. Hence, by the `strong uniqueness property' (\ref{eq:strong-uniqueness-2}), we have $q \circ \alpha = q$, so $\alpha \in \CT(q)$. Therefore, $\CT(q)$ acts transitively on $q^{-1}(0)$, as required. Hence, $q$ is a normal covering map from $\mathbb{L}^2$ to $G$. This completes the proof of Theorem \ref{thm:cover-2}.
\end{proof}

We will use a similar (but slightly more intricate) argument to prove Theorem \ref{thm:cover-d}. We will need the following (slightly strengthened) analogue of Claim \ref{claim:exist-unique2}.
\begin{claim}
\label{claim:exist-unique}
Let $d \in \mathbb{N}$ with $d \geq 2$. If $S \subset \mathbb{Z}^d$, let $N(S) := N_{\mathbb{L}^d}(S)$ denote the neighbourhood of $S$ in the graph $\mathbb{L}^d$. Let $G$ be a connected graph which is weakly $3$-locally $\mathbb{L}^d$. Let $p_0:\{0\} \cup \{\pm e_i:\ i \in [d]\} = N(0) \to V(G)$ be an injection such that $p_0(e_i)$ and $p_0(-e_i)$ are opposite one another across $p_0(0)$, for each $i \in [d]$. Let $P$ be a geodesic (in $\mathbb{L}^d$) from $0$ to some other point $x \in \mathbb{Z}^d$. Then there is a unique way of extending $p_0$ to a map $p:N(P) \to V(G)$ such that
\begin{enumerate}
\item For all $w \in N(P)$, the restriction $p\,|\,N(w) \cap N(P)$ is a injective graph homomorphism from $\mathbb{L}^d[N(w) \cap N(P)]$ into $G$, and
\item For all $u \in P$, if $a_1,a_2 \in \mathbb{Z}^d$ are opposite one another across $u$, then $p(a_1)$ and $p(a_2)$ are opposite one another across $p(u)$.
\end{enumerate}
\end{claim}
\begin{proof}[Proof of Claim \ref{claim:exist-unique}.]
Let $P = (x_0, x_1,\ldots, x_l)$, where $x_0 =0$ and $x_l=x$. For each $k \in [l]$, let $P_k$ denote the sub-path of $P$ between $0$ and $x_k$. Without loss of generality, we may assume that $x$ lies in the positive orthant, i.e. all of its coordinates are non-negative. Then, since $(x_i)_{i=0}^{l}$ is a geodesic, each $x_i$ lies in the positive orthant also, and furthermore $x_i - x_{i-1} \in \{e_j:\ j \in [d]\}$ for all $i$.

We will prove that the claim holds for $P_k$, for all $k \leq l$, by induction on $k$. By definition, it holds for $P_0$. Assume that it holds for $P_{k-1}$, where $k \geq 1$; we will prove that it holds for $P_k$. Let $p$ be an extension of $p_0$ to $N(P_{k-1})$, satisfying the conclusion of the claim when $P$ is replaced by $P_{k-1}$; we will show that there is a unique way to extend $p$ to $N(P_k)$ in such a way that the conclusion of the claim holds when $P$ is replaced by $P_k$.

Note that $x_k - x_{k-1} = e_j$ for some $j \in [d]$. Without loss of generality, we may assume that $x_k - x_{k-1} = e_1$. For brevity, let us write $v:=x_{k-1}$. \begin{comment} Note that by the induction hypothesis, $p(v+e_i)$ is opposite $p(v-e_i)$ across $p(v)$ for all $i \in [d]$. \end{comment}

We split into two cases.

\begin{description}
\item[case 1:] $k > 1$ and $x_{k-1}-x_{k-2} = e_j$ for some $j \geq 2$;
\item[case 2:] $k=1$, or $x_{k-1}-x_{k-2} =e_1$.
\end{description}
First assume we are in case 1. Without loss of generality, we may assume that $j=2$, so $x_{k-1}-x_{k-2} = e_2$. Then we must define $p$ on the set of $2d-2$ `extra' vertices
$$\mathcal{E}:=N(P_k) \setminus N(P_{k-1}) = \{v+e_1+e_i:\ i \in [d]\} \cup \{v+e_1-e_i:\ i \geq 3\}.$$
Note that we have already defined $p$ at $v$, at $v+e_i$ for all $i \in [d]$, at $v-e_i$ for all $i \in [d]$, and at $v+e_1-e_2$, in such a way that $p(v+e_i)$ is opposite $p(v-e_i)$ across $v$, for all $i \in [d]$. Hence, we have already defined $p(v)$ and $p(v+e_1-e_2)$, but we have not yet defined $p$ at any other neighbour of $v+e_1$. For each $i \geq 2$, $p(v+e_1)$ and $p(v+e_i)$ are not opposite one another across $p(v)$, so they have exactly two common neighbours, namely $p(v)$ and one other vertex. We must define $p(v+e_1+e_i)$ to be this other vertex. Similarly, for each $i \geq 3$, $p(v+e_1)$ and $p(v-e_i)$ are not opposite one another across $p(v)$, so they have exactly two common neighbours, namely $p(v)$ and one other vertex. We must define $p(v+e_1-e_i)$ to be this other vertex. Then the $2d-1$ vertices
$$\{p(v+e_1+e_i):\ i \in [d-1]\} \cup \{p(v+e_1-e_i):\ i \in [d]\}$$
are distinct neighbours of $p(v+e_1)$, by Observation \ref{observation:opposite} (applied with $u=v$). We now assert that for each $i \geq 2$, $p(v+e_1+e_i)$ and $p(v+e_1-e_i)$ are opposite one another across $p(v+e_1)$. To see this, observe that $p(v+e_i)$ and $p(v-e_i)$ are opposite one another across $p(v)$, and that $p(v)$ and $p(v+e_1+e_i)$ are the two common neighbours of $p(v+e_1)$ and $p(v+e_i)$, and that $p(v)$ and $p(v+e_1-e_i)$ are the two common neighbours of $p(v+e_1)$ and $p(v-e_i)$. Hence, by Remark \ref{remark:3locally}, $p(v+e_1+e_i)$ and $p(v+e_1-e_i)$ are opposite one another across $p(v+e_1)$, proving the assertion.

It remains to define $p(v+2e_1)$. We have already defined $p$ on the other $2d-1$ neighbours of $v+e_1$, in such a way that the images are distinct neighbours of $p(v+e_1)$; there is just one more neighbour of $p(v+e_1)$, and we must define $p(v+2e_1)$ to be this vertex. Then $p(v+2e_1)$ and $p(v)$ must be opposite one another across $p(v)$, by Observation \ref{observation:opposite}. Hence, property (2) of Claim \ref{claim:exist-unique} holds for $P_k$.

We must now check property (1) of the claim, for $P_k$. Note that $d(0,w) \geq k-2$ for any $w \in N(\mathcal{E})$, whereas $d(0,w) \leq k-3$ for any $w \in N(P_{k-4})$, so $N(\mathcal{E}) \cap N(P_{k-4}) = \emptyset$. Hence, given the inductive hypothesis, it suffices to check that $p|N(\{x_{k-3},x_{k-2},x_{k-1},x_k\})$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{x_{k-3},x_{k-2},x_{k-1},x_k\})]$ to $G$.

We have $x_{k} = v+e_1$, $x_{k-1} = v$, $x_{k-2} = x-e_2$ and (if $k \geq 3$) $x_{k-3} = v-e_2-e_s$ for some $s \in [d]$. Observe that 
$$N(\{x_{k-3},x_{k-2},x_{k-1},x_k\}) = N(\{v-e_2-e_s,v-e_2,v,v+e_1\}) \subset B_3(v,\mathbb{L}^d).$$

By Observation \ref{obs:bijective-homomorphism}, there exists a bijective graph homomorphism $\psi:\Link_3(\mathbb{L}^d,v) \to \Link_3(G,p(v))$ with $\psi(v) = p(v)$. Since $p(v+e_i)$ is opposite $p(v - e_i)$ across $p(v)$ for all $i \in [d]$, and $\psi(v+e_i)$ is opposite $\psi(v-e_i)$ across $\psi(v)$ for all $i \in [d]$, we may choose $\psi$ to agree with $p$ on $N(v)$. (Simply replace $\psi$ with $\psi \circ \alpha$, for an appropriate $\alpha \in \Aut(\mathbb{L}^d)$. More specifically, we may take $\alpha = t_{v} \circ g \circ t_v^{-1}$, where $t_v$ denotes translation by $v$, and $g$ is the appropriate element of $B_d$.) But note from the first part of the proof that, given {\em only} the values of $p$ on $N(v)$, there was at most one way of extending $p$ to $N(\{v,v+e_1\})$ in such a way that $p|N(\{v,v+e_1\})$ was an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v+e_1\})]$ to $G$. Certainly, $\psi|N(\{v,v+e_1\})$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v+e_1\})]$ to $G$, and it agrees with $p$ on $N(v)$. Hence, $p$ agrees with $\psi$ on all of $N(\{v,v+e_1\})$. By exactly the same argument (in `reverse'), if $q:\Link_1(v,\mathbb{L}^d) \to G$ is any injective graph homomorphism such that $q(v+e_i)$ is opposite $q(v-e_i)$ across $q(v)$ for all $i \in [d]$, then there is at most one way of extending $q$ to $N(\{v,v-e_2,v-e_2-e_s\}) = N(\{x_{k-1},x_{k-2},x_{k-3}\})$ in such a way that $q$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v-e_2,v-e_2-e_s\})]$ to $G$. By definition, $\psi$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v-e_2,v-e_2-e_s\})]$ to $G$, and it agrees with $p$ on $N(v)$; hence, setting $q = p|N(v)$, we see that $p$ must agree with $\psi$ on all of $N(\{v,v-e_2,v-e_2-e_s\})$. Therefore, $p$ agrees with $\psi$ on $N(\{v-e_2-e_s,v-e_2,v,v+e_1\})$, so $p$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v-e_2-e_s,v-e_2,v,v+e_1\})]$ to $G$, as required.

Now assume that we are in case 2. Note that we have already defined $p$ at $v$, at $v+e_i$ for all $i \in [d]$, at $v-e_i$ for all $i \in [d]$, in such a way that $p(v+e_i)$ is opposite $p(v-e_i)$ across $v$, for all $i \in [d]$. Note that we have already defined $p(v)$, but we have not yet defined $p$ at any other neighbour of $v+e_1$. We must therefore define $p$ on the set of $2d-1$ `extra' vertices
$$\mathcal{E}:=N(P_k) \setminus N(P_{k-1}) = \{v+e_1+e_i:\ i \in [d]\} \cup \{v+e_1-e_i:\ i \geq 2\}.$$
For each $i \geq 2$, $p(v+e_1)$ and $p(v+e_i)$ are not opposite one another across $p(v)$, so they have exactly two common neighbours, namely $p(v)$ and one other vertex. We must define $p(v+e_1+e_i)$ to be this other vertex. Similarly, for each $i \geq 2$, $p(v+e_1)$ and $p(v-e_i)$ are not opposite one another across $p(v)$, so they have exactly two common neighbours, namely $p(v)$ and one other vertex. We must define $p(v+e_1-e_i)$ to be this other vertex.
Then the $2d-1$ vertices
$$\{p(v+e_1+e_i):\ i \in [d-1]\} \cup \{p(v+e_1-e_i):\ i \in [d]\}$$
are distinct neighbours of $p(v+e_1)$, by Observation \ref{observation:opposite}. We assert that, for each $i \geq 2$, $p(v+e_1+e_i)$ and $p(v+e_1-e_i)$ are opposite one another across $p(v+e_1)$. Indeed, the proof of this is exactly as in case 1.

It remains to define $p(v+2e_1)$. We have already defined $p$ on the other $2d-1$ neighbours of $v+e_1$, in such a way that the images are distinct neighbours of $p(v+e_1)$; there is just one more neighbour of $p(v+e_1)$, and we must define $p(v+2e_1)$ to be this vertex. Then $p(v+2e_1)$ and $p(v)$ must be opposite one another across $p(v)$, by Observation \ref{observation:opposite}. Hence, property (2) of Claim \ref{claim:exist-unique} holds for $P_k$.

It remains to check (1) of the claim, for $P_k$. Note that $d(0,w) \geq k-2$ for any $w \in N(\mathcal{E})$, whereas $d(0,w) \leq k-3$ for any $w \in N(P_{k-4})$, so $N(\mathcal{E}) \cap N(P_{k-4}) = \emptyset$. Hence, given the inductive hypothesis, it suffices to check that $p|N(\{x_{k-3},x_{k-2},x_{k-1},x_k\})$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{x_{k-3},x_{k-2},x_{k-1},x_k\})]$ to $G$. This part of the argument is almost exactly as in case 1, so we omit it.\begin{comment}



We have $x_{k-1} = v$, $x_{k} = v+e_1$, $x_{k-2} = x-e_1$ and (if $k \geq 3$) $x_{k-3} = v-e_1-e_s$ for some $s \in [d]$. Observe that 
$$N(\{x_{k-3},x_{k-2},x_{k-1},x_k\}) = N(\{v-e_1-e_s,v-e_1,v,v+e_1\}) \subset B_3(v,\mathbb{L}^d).$$
By Observation \ref{obs:bijective-homomorphism}, there exists a bijective graph homomorphism $\psi:\Link_3(\mathbb{L}^d,v) \to \Link_3(G,p(v))$ with $\psi(v) = p(v)$. Since $p(v+e_i)$ is opposite $p(v - e_i)$ across $p(v)$ for all $i \in [d]$, and $\psi(v+e_i)$ is opposite $\psi(v-e_i)$ across $\psi(v)$ for all $i \in [d]$, we may choose $\psi$ to agree with $p$ on $N(v)$. But note from the first part of the proof that, given {\em only} the values of $p$ on $N(v)$, there was at most one way of extending $p$ to $N(\{v,v+e_1\})$ in such a way that $p|N(\{v,v+e_1\})$ was an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v+e_1\})]$ to $G$. Certainly, $\psi|N(\{v,v+e_1\})$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v+e_1\})]$ to $G$, and it agrees with $p$ on $N(v)$. Hence, $p$ agrees with $\psi$ on all of $N(\{v,v+e_1\})$. By exactly the same argument (in `reverse'), if $q:\Link_1(v,\mathbb{L}^d) \to G$ is any injective graph homomorphism such that $q(v+e_i)$ is opposite $q(v-e_i)$ across $q(v)$ for all $i \in [d]$, then there is at most one way of extending $q$ to $N(\{v,v-e_1,v-e_1-e_s\}) = N(\{x_{k-1},x_{k-2},x_{k-3}\})$ in such a way that $q$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v-e_1,v-e_1-e_s\})]$ to $G$. By definition, $\psi$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v,v-e_1,v-e_1-e_s\})]$ to $G$, and it agrees with $p$ on $N(v)$; hence, setting $q = p|N(v)$, we see that $p$ must agree with $\psi$ on all of $N(\{v,v-e_1,v-e_1-e_s\})$. Therefore, $p$ agrees with $\psi$ on $N(\{v-e_1-e_s,v-e_1,v,v+e_1\})$, so $p$ is an injective graph homomorphism from $\mathbb{L}^d[N(\{v-e_1-e_s,v-e_1,v,v+e_1\})]$ to $G$, as required. This completes the proof of Claim \ref{claim:exist-unique}.
\end{comment}
\end{proof}

We can now prove Theorem \ref{thm:cover-d}.
\begin{proof}[Proof of Theorem \ref{thm:cover-d}.]
Let $G$ be a connected graph which is weakly $3$-locally $\mathbb{L}^d$. Choose any vertex $v_0 \in V(G)$ and define $p_0(0) = v_0$. By Observation \ref{obs:bijective-homomorphism}, there exists a bijective graph homomorphism $\phi:\Link_3(0,\mathbb{L}^d) \to \Link_3(v_0,G)$ with $\phi(0) = v_0$. Define $p_0(e_i) = \phi(e_i)$ and $p_0(-e_i) = \phi(-e_i)$ for all $i \in [d]$.

Now we extend $p_0$ to a map $q$ on all of $\mathbb{Z}^d$, as follows. For each $x \in \mathbb{Z}^d$, choose a geodesic $P$ from $0$ to $x$. Since $p_0$ satisfies the hypothesis of Claim \ref{claim:exist-unique}, we can extend $p_0$ to a map $p_{P}$ from $N(P)$ to $V(G)$ with properties (1) and (2) of Claim \ref{claim:exist-unique}. We define $q(x)=p_{P}(x)$.

Our next aim is to prove:
\begin{equation} \label{eq:well-defined-d} p_{P}(x) \textrm{ is independent of the choice of geodesic }P \textrm{ from }0 \textrm{ to } x.\end{equation}

To prove (\ref{eq:well-defined-d}), we may assume without loss of generality that $x$ is in the positive quadrant. Observe that for any two geodesics $P,P'$ from $0$ to $x$, we can get from $P$ to $P'$ by a sequence of `elementary switches', now meaning operations which replace some sub-path $(v,v+e_i,v+e_i+e_j)$ by the sub-path $(v,v+e_j,v+e_i+e_j)$, for some $i \neq j$. Hence, it suffices to show that if $P$ and $P'$ differ from one another by an elementary switch, then we have $p_{P}(x) = p_{P'}(x)$. Suppose then that $P = (v_0,v_1,\ldots,v_k,v_{k}+e_i,v_{k}+e_i+e_j,v_{k+3},\ldots, v_l)$ and $P' = (v_0,v_1,\ldots,v_k,v_{k}+e_j,v_{k}+e_i+e_j,v_{k+3},\ldots,v_l)$, where $v_0 = 0$ and $v_l=x$. Without loss of generality, we may assume that $i=1$ and $j=2$. For brevity, let us define $p := p_{P}$ and $p' := p_{P'}$, and let us write $v_k = v$. 

We have $p(v) = p'(v)$ and $p(v+e_i) = p'(v+e_i)$ for all $i \in [d]$, since $P'_k = P_k$ and $p$ is uniquely determined on $N(P_k)$ (and $p'$ on $N(P'_k)$). By Observation \ref{obs:bijective-homomorphism}, there exists a bijective graph homomorphism $\psi: \Link_3(\mathbb{L}^d,v) \to \Link_3(G,p(v))$ with $\psi(v) = p(v)$. Since $p(v+e_i)$ is opposite $p(v - e_i)$ across $p(v)$ for all $i \in [d]$, we may choose $\psi$ to agree with $p$ (and $p'$) on $N(v)$. Since both $\psi$ and $p$ satisfy the hypothesis of Claim \ref{claim:exist-unique} with $v$ replacing $0$ and with $P = (v,v+e_1,v+e_1+e_2)$, it follows that $p$ and $\psi$ agree with one another on $N(\{v,v+e_1,v+e_1+e_2\})$. Since both $\psi$ and $p'$ satisfy the hypothesis of Claim \ref{claim:exist-unique} with $v$ replacing $0$ and with $P = (v,v+e_2,v+e_1+e_2)$, it follows that $p'$ and $\psi$ agree with one another on $N(\{v,v+e_2,v+e_1+e_2\})$. Hence, $p$ and $p'$ agree with one another on $N(v+e_1+e_2)$. In both cases, we have $p=p'$ on $N(v_{k+2})$. By the uniqueness part of Claim \ref{claim:exist-unique} (applied with $v_{k+2}$ in place of $0$), it follows that $p = p'$ on $(v_{k+2},v_{k+3},\ldots,v_l)$, so in particular $p(x) = p'(x)$, proving (\ref{eq:well-defined-d}).

By (\ref{eq:well-defined-d}) and property (1) of Claim \ref{claim:exist-unique}, $q|N(v)$ is an injective graph homomorphism from $\mathbb{L}^d[N(v)]$ to $G$ for all $v \in \mathbb{Z}^d$; this says precisely that $q$ is a covering map from $\mathbb{L}^d$ to $G$. By Lemma \ref{lemma:condition}, any covering map from $\mathbb{L}^d$ to $G$ must satisfy property (2) of Claim \ref{claim:exist-unique}. Hence, the uniqueness part of Claim \ref{claim:exist-unique} implies a `strong uniqueness property':
\begin{equation}
\label{eq:strong-uniqueness-d} 
q \textrm{ is the unique covering map from }\mathbb{L}^d \textrm{ to } G \textrm{ agreeing with }p_0 \textrm{ on }N(0).\end{equation}
As in the $d=2$ case, this implies that $q$ is a normal covering map. To see this, it suffices to show that the group of covering transformations of $q$ is transitive on the fibre $q^{-1}(0)$. So let $v \in \mathbb{Z}^2 \setminus \{0\}$ with $q(v) = q(0)$. By Lemma \ref{lemma:condition}, $q(e_i)$ and $q(-e_i)$ are opposite one another across $q(0)$ for all $i \in [d]$, and $q(v+e_i)$ and $q(v-e_i)$ are opposite one another across $q(v)=q(0)$ for all $i \in [d]$. Hence, we have
$$\{\{q(v+e_i),q(v-e_i)\}:\ i \in [d]\} = \{\{q(e_i),q(-e_i)\}:\ i \in [d]\}.$$
Since $\Aut(\mathbb{L}^d) = T(\mathbb{Z}^d) \rtimes B_d$, and the elements of $B_d$ correspond precisely to the permutations of $\{\pm e_i:\ i \in [d]\}$ which preserve the partition
$$\{\{e_i,-e_i\}:\ i \in [d]\}$$
(see Fact \ref{fact:aut-ld}), we may choose $\alpha \in \Aut(\mathbb{L}^d)$ such that $\alpha(0) = v$ and $q(w) = q(\alpha(w))$ for all $w \in \Gamma(0)$. (Take $\alpha = g \circ t_v$, where $t_v$ is translation by $v$ and $g$ is the appropriate element of $B_d$.)

Observe that $q \circ \alpha$ is a covering map from $\mathbb{L}^d$ to $G$ which agrees with $q$ (and therefore with $p_0$) on $N(0)$. Hence, by the `strong uniqueness property' (\ref{eq:strong-uniqueness-d}), we have $q \circ \alpha = q$, so $\alpha \in \CT(q)$. Therefore, $\CT(q)$ acts transitively on $q^{-1}(0)$, as required. Hence, $q$ is a normal covering map from $\mathbb{L}^d$ to $G$. This completes the proof of Theorem \ref{thm:cover-d}.
\end{proof}

\begin{example}
\label{example:Ld}
We now give an example showing that Theorem \ref{thm:cover-d} is best possible, in the sense that for every integer $d \geq 3$, there exists a finite, connected graph which is $2$-locally-$\mathbb{L}^d$ but which is not covered by $\mathbb{L}^d$. We first deal with the case $d=3$.

Let us recall some more group-theoretic notions. If $\Gamma$ is a group, and $S \subset \Gamma$ with $\Id \notin S$ and $S^{-1}=S$, the {\em (right) Cayley graph of $G$ with respect to $S$} is the graph with vertex-set $G$ and edge-set
$$\{\{g,gs\}:\ g \in \Gamma,\ s \in S\}.$$
It is sometimes denoted by $\Cay(\Gamma,S)$.

We write finitely presented groups in the form
$$\langle a_1,a_2,\ldots,a_s;\ R_1, \ldots, R_N \rangle$$
where $a_1,\ldots,a_s$ are the {\em generators} and $R_1,\ldots,R_N$ are the {\em relations} (i.e., $R_i$ is an equation of the form $w_i=w_i'$, where $w_i$ and $w_i'$ are words in $a_1,\ldots,a_s$ and their inverses).\begin{comment} Let $F_{a_1,\ldots,a_s}$ be the free group with generators $a_1,\ldots,a_s$. Formally, a group $\Gamma$ is said to have presentation
$$\langle a_1,a_2,\ldots,a_s;\ w_1 = w_1', \ldots, w_N =w_N'\rangle$$
if $\Gamma$ is isomorphic to the quotient of $F_{a_1,\ldots,a_s}$ by the normal subgroup $\langle w_i w_i^{-1}:\ i \in [N] \rangle$. \end{comment}

If $\Gamma$ is a finitely presented group with generators $a_1,\ldots,a_s$, the {\em length} of the word
$$a_{i_1}^{r_1} a_{i_2}^{r_2} \ldots a_{i_t}^{r_t}$$
is defined to be $\sum_{i=1}^{t}|r_i|$; for example, $a_1^{-2} a_2^2 a_2^{-1}$ has length 5. A {\em relator} is a word which evaluates to the identity in $\Gamma$. A relator is {\em trivial} if it evaluates to the identity in the free group with generators $a_1,a_2,\ldots,a_s$. For example, the trivial relators of length two are $a_i a_i^{-1}$ and $a_i^{-1}a_i$ (for $i \in [s]$).

Let $\Gamma$ be the finitely presented group with three generators defined by
\begin{equation}
\label{eq:pres}
\Gamma = \langle a,b,c ;\ a^{-1} b = c^2, b^{-1}c = a^2, c^{-1}a = b^2\rangle,
\end{equation}
and let $G = \Cay(\Gamma,\{a,b,c,a^{-1},b^{-1},c^{-1}\})$, i.e. $G$ is the graph of the finitely presented group $\Gamma$ with respect to the generators $a,b,c$. It can be checked (e.g. using a computer algebra system) that $\Gamma$ is a finite group, and in fact that $\Gamma \cong \mathbb{F}_2^4 \rtimes C_7$, so $|\Gamma|=112$. A concrete realisation of $\Gamma$ is the group
$$ T(\mathbb{F}_2^4) \rtimes \langle M \rangle \leq \Aff(\mathbb{F}_2^4),$$
where $\Aff(\mathbb{F}_2^4)$ denotes the group of all affine transformations of the vector space $\mathbb{F}_2^4$, i.e.
$$\Aff(\mathbb{F}_2^4) = \{(x \mapsto Ax+v):\ A \in \GL(\mathbb{F}_2^4),\ v \in \mathbb{F}_2^4\},$$
$$T(\mathbb{F}_2^4) = \{(x \mapsto x+v):\ v \in \mathbb{F}_2^4\} \leq \Aff(\mathbb{F}_2^4)$$
denotes the subgroup of all translations, and
$$M = \left( \begin{array}{cccc}0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1\end{array} \right).$$
Note that $M^7 = \Id$, so $\langle M \rangle \leq \GL(\mathbb{F}_2^4)$ is a cyclic group of order 7. We may take the generators $a,b,c$ to be
\begin{align*} a & = (x \mapsto Mx + (1,0,0,1)^{\top}),\\
b & = (x \mapsto M^2x + (1,0,1,1)^{\top}),\\
c & = (x \mapsto M^4 x + (0,1,0,1)^{\top}),\end{align*}
where we compose these functions from left to right, so that $(a \cdot b)(x) = b(a(x))$.

We now find the Abelianisation of $\Gamma$, i.e. the quotient group $\Gamma/[\Gamma,\Gamma]$, where
$$[\Gamma,\Gamma] : = \{ghg^{-1}h^{-1}:\ g,h \in \Gamma\}$$
denotes the commutator subgroup of $\Gamma$. Let $\bar{a},\bar{b},\bar{c}$ denote the images of $a,b,c$ in the Abelianization of $\Gamma$. Then, from the second relation, we have $\bar{c} = \bar{a}^2 \bar{b}$; substituting this into the first relation gives $\bar{b} = \bar{a} \bar{c}^2 = \bar{a} \bar{a}^4 \bar{b}^2$, so $\bar{b} = \bar{a}^{-5}$. Substituting this back into the second relation gives $\bar{c} = \bar{a}^2 \bar{b} = \bar{a}^{-3}$. The third relation then gives $1=\bar{c}^{-1} \bar{a} \bar{b}^{-2} = \bar{a}^3 \bar{a} \bar{a}^{10} = \bar{a}^{14}$. Hence, 
$$\Gamma/[\Gamma,\Gamma] = \langle \bar{a} \rangle \cong C_{14},$$
a cyclic group of order 14, and we have
$$\bar{b} = \bar{a}^9, \quad \bar{c} = \bar{a}^{11}, \quad \bar{a}^{-1} = \bar{a}^{13},\quad \bar{b}^{-1} = \bar{a}^5,\quad \bar{c}^{-1} = \bar{a}^3.$$
Since each of $\bar{a},\bar{b},\bar{c}$ is an odd power of $\bar{a}$, there is no relator of odd length (in $\bar{a},\bar{b},\bar{c}$ and their inverses) in $\Gamma/[\Gamma,\Gamma]$, and so there is no relator of odd length in the group $\Gamma$. Hence, $G$ has no odd cycle. In particular, $G$ has no cycle of length 3 or 5. Moreover, $\bar{a},\bar{b},\bar{c},\bar{a}^{-1},\bar{b}^{-1},\bar{c}^{-1}$ are all distinct elements of $\Gamma/[\Gamma,\Gamma]$. Hence, $a,b,c,a^{-1},b^{-1},c^{-1}$ are all distinct elements of $\Gamma$, so $G$ is $6$-regular. 

It can be checked that for the group $\Gamma$, the only relators of length 4 are the 24 relators arising from rearranging the relations in (\ref{eq:pres}) and taking inverses. (We suppress the details of this calculation, as it is straightforward but somewhat long; it can easily be done using a computer algebra system.) Hence, the following words of length2 appear in no non-trivial relator of length 4:
\begin{equation} \label{eq:opposite} ab,bc,ca,b^{-1}a^{-1},c^{-1}b^{-1},a^{-1}c^{-1} \end{equation}
all the other non-trivial words of length two appear as the initial two letters of exactly one non-trivial relator of length 4.

It follows that $G$ is $2$-locally-$\mathbb{L}^3$. Indeed, since $G$ is vertex-transitive, it suffices to check this at the vertex $\Id$, only. In other words, we must construct a map $\psi:B_2(0,\mathbb{L}^3) \to V(G)$ which is an isomorphism from $\Link_2(0,\mathbb{L}^2)$ to $\Link_2(\textrm{Id},G)$, with $\psi(0)=\textrm{Id}$.

Let $S : = \{a,b,c,a^{-1},b^{-1},c^{-1}\}$. Let us say that two distinct elements $x,y \in S$ are {\em complementary} if $x^{-1}y$ appears in no non-trivial relator of length 4. (Note that this relation is symmetric, as $x^{-1}y$ appears in the list (\ref{eq:opposite}) if and only if $y^{-1}x$ does. Moreover, each element of $S$ is complementary to exactly one other element of $S$.) We can construct an appropriate map $\psi$ by choosing the six images $\psi(\pm e_i)$ to be distinct elements of $S$, in such a way that $\psi(e_i)$ and $\psi(-e_i)$ are complementary for each $i \in \{1,2,3\}$. For $i \neq j$ and $s,t \in \{\pm 1\}$, we can then define $\psi(se_i + te_j)$ as follows. Let $x = \psi(se_i)$ and $y = \psi(te_j)$. Then $x$ and $y$ are distinct and not complementary, so $x^{-1}y$ appears as the initial two letters of exactly one non-trivial relator of length 4, say $x^{-1} y u v = \Id$. Define $\psi(se_i + te_j) = yu\ (= xv^{-1})$. Finally, for each $i$ and each $s \in \{\pm 1\}$, define $\psi(2se_i)$ as follows. Let $x = \psi(se_i)$. Let $y$ be the unique element of $S$ such that $x^{-1}$ and $y$ are complementary, and define $\psi(2se_i) = xy$. 

An explicit choice of $\psi$ is as follows.
\begin{align*} \psi(0) & = \textrm{Id},\\
\psi(e_1) & = a,\\
\psi(-e_1) & = c^{-1},\\
\psi(e_2) & = b,\\
\psi(-e_2) & = a^{-1},\\
\psi(e_3) & = c,\\
\psi(-e_3) & = b^{-1},
\end{align*}
\begin{align*}
\psi(e_1+e_2) & = ac = bc^{-1},\\
\psi(e_1-e_2) & = ac^{-1} = a^{-1}b^{-1},\\
\psi(-e_1+e_2) &= c^{-1}a = b^2,\\
\psi(-e_1-e_2) &= c^{-1}b = a^{-2},\\
\psi(e_1+e_3) &= ab^{-1} = cb,\\
\psi(e_1-e_3)&= a^2 = b^{-1}c,\\
\psi(-e_1+e_3)& = c^{-1}a^{-1} = cb^{-1},\\
\psi(-e_1-e_3) &= c^{-2} = b^{-1}a,\\
\psi(e_2+e_3) &= ca^{-1}=ba,\\
\psi(e_2-e_3)&= ba^{-1} = b^{-1}c^{-1},\\
\psi(-e_2+e_3)& = a^{-1}b = c^2,\\
\psi(-e_2-e_3) &= a^{-1}c = b^{-2},
\end{align*}
\begin{align*}
\psi(2e_1) & = ab,\\
\psi(-2e_1)&=c^{-1}b^{-1},\\
\psi(2e_2)&= bc,\\
\psi(-2e_2)&=a^{-1}c^{-1},\\
\psi(2e_3) &= ca,\\
\psi(-2e_3) &= b^{-1}a^{-1}.\end{align*}
Using the facts that $G$ has no 3-cycle or 5-cycle, together with (\ref{eq:opposite}), it is easy to see that $\psi$ is an isomorphism from $\Link_2(0,\mathbb{L}^2)$ to $\Link_2(\textrm{Id},G)$. We may conclude that $G$ is 2-locally-$\mathbb{L}^3$.
\begin{comment} We note that in $G$, $a$ and $c^{-1}$ are opposite one another across $\textrm{Id}$, as are $b$ and $a^{-1}$, and $c$ and $b^{-1}$. \end{comment}

On the other hand, we claim that $G$ is not covered by $\mathbb{L}^3$. Indeed, suppose for a contradiction that $p:\mathbb{L}^3 \to G$ is a cover map. By considering $p \circ \phi$ for some $\phi \in \Aut(\mathbb{L}^3)$ if necessary, we may assume that $p(0) = \textrm{Id}$ and $p(e_1)=a$. By Lemma \ref{lemma:condition}, $p(-e_1)$ must be opposite $p(e_1)=a$ across $p(0)=\textrm{Id}$, so $p(-e_1) = c^{-1}$. By considering $p \circ \phi$ for some $\phi \in \Aut(\mathbb{L}^3)$ fixing the $x$-axis, if necessary, we may assume that $p(e_2) = b$. Then, by Lemma \ref{lemma:condition}, $p(-e_2)$ must be opposite $p(e_2)=b$ across $p(0)=\textrm{Id}$, so $p(-e_2) = a^{-1}$. 

The only common neighbours of $p(e_1)=a$ and $p(e_2)=b$ are $\textrm{Id}$ and $ac=bc^{-1}$. Hence, we must have $p(e_1+e_2) = ac=bc^{-1}$ (clearly, $p(e_1 + e_2) \neq \textrm{Id}$, as $p$ must be bijective on $\Gamma(e_1)$). Similarly, the only common neighbours of $p(e_1)=a$ and $p(-e_2)=a^{-1}$ are $\textrm{Id}$ and $ac^{-1}=a^{-1}b^{-1}$, so we must have $p(e_1-e_2) = ac^{-1}=a^{-1}b^{-1}$. But then $p(e_1+e_2)$ and $p(e_1-e_2)$ have two common neighbours, namely $a$ and $ac^{-1}a^{-1} = acb^{-1}$, so they are not opposite one another, contradicting Lemma \ref{lemma:condition}. Hence, $G$ is not covered by $\mathbb{L}^3$, as claimed.

For $d \geq 4$, we let $\Gamma_d = \Gamma \times \mathbb{Z}_{14}^{d-3}$, and $G_d = \Cay(\Gamma_d,S_d)$ where
\begin{align*} S_d & = \{(a,0),(b,0),(c,0),(a^{-1},0),(b^{-1},0),(c^{-1},0)\}\\
& \cup \{(\textrm{Id},f_i):\ i \in [d-3]\} \cup \{(\textrm{Id},-f_i):\ i \in [d-3]\}),\end{align*}
and where $f_i = (0,0,\ldots,0,1,0,\ldots,0) \in \mathbb{Z}_{14}^{d-3}$ denotes the $i$th unit vector in $\mathbb{Z}_{14}^{d-3}$. It is easy to see (using the $d=3$ case) that $G_d$ is $2$-locally $\mathbb{L}^d$, but is not covered by $\mathbb{L}^d$.
\end{example}

\section{A geometrical proof of Theorem \ref{thm:cover-wheel}}
In this section, we prove Theorem \ref{thm:cover-wheel}, using arguments more geometric than those in the previous section. (This automatically gives an alternative proof of the finite-graph case of Theorem \ref{thm:cover-2}.) We feel this proof to be of independent interest, though it does not generalise to produce an alternative proof of Theorem \ref{thm:cover-d}.

We will need to use the following result.

\begin{lemma}
\label{lemma:uniqueness}
If a graph $G$ is a 4-regular quadrangulation of $\mathbb{R}^2$, then $G$ is isomorphic (as a quadrangulation of $\mathbb{R}^2$) to $\mathbb{L}^2$.
\end{lemma}

After finding a proof of this lemma, we learned that, unsurprisingly, it was well-known to topological graph theorists. However, we were unable to find a proof in the literature, so for completeness, we present two proofs in the Appendix: one using covering spaces, due to \'E. Colin de Verdi\`ere \cite{colin-personal}, and one combinatorial, due to Nakamoto \cite{nakamoto-personal}.

We now prove Theorem \ref{thm:cover-wheel}.

\begin{proof}[Proof of Theorem \ref{thm:cover-wheel}.]
Let $G$ be as in the statement of the theorem. Let $\mathcal{C}$ be a collection of 4-cycles of $G$ as in the definition of the 4-cycle wheel property. Note that each edge of $G$ is contained in exactly two of the 4-cycles in $\mathcal{C}$. Moreover, each vertex of $G$ is contained in exactly four of the 4-cycles in $\mathcal{C}$.

We use $G$ to define a polyhedral surface $S$, as follows. For each $C \in \mathcal{C}$, let $s_C$ be a closed square in $\mathbb{R}^2$ of unit side-length, such that $s_C \cap s_{C'} = \emptyset$ for all distinct $C,C' \in \mathcal{C}$. For each cycle $C = v_1v_2v_3v_4v_1 \in \mathcal{C}$, label the corners of $s_C$ with the vertices of $C$, in the cyclic order $v_1,v_2,v_3,v_4$. Let $S$ be quotient space of
$$\bigcup_{C \in \mathcal{C}} s_C$$
under the following identification. For each edge $e = uv \in E(G)$, let $C$ and $C'$ be the two 4-cycles in $\mathcal{C}$ containing $e$. Identify the side of $C$ labelled with $u$ and $v$ with the side of $C'$ labelled with $u$ and $v$ (identifying the two corners labelled with $u$, and the two corners labelled with $v$). Clearly, $S$ is a compact surface, and it is connected, since $G$ is connected. Let
$$q: \bigcup_{C \in \mathcal{C}} s_C \to S$$
denote the quotient map. 

Note that an isomorphic copy $G'$ of the graph $G$ is embedded on $S$, and forms a quadrangulation of $S$ whose face-cycles are precisely the 4-cycles in $\mathcal{C}$, and whose closed faces are $\{q(s_{C}):\ C \in \mathcal{C}\}$; moreover, for each $C \in \mathcal{C}$, $q|s_{C}$ is a homeomorphism. 

It follows that each edge of $G'$ is incident with exactly two faces of $G'$, and each vertex of $G'$ is incident with exactly four faces of $G'$. Let $v(G')$, $e(G')$ and $f(G')$ denote the number of vertices, edges and faces of $G'$ respectively. We have $4v(G') = 4f(G')$ (counting the number of times a vertex is incident with a face) and $2e(G') = 4f(G')$ (counting the number of times an edge is contained in a face-cycle). Hence, the Euler characteristic of the surface $S$ is
$$\chi(S) = v(G') - e(G') + f(G') = 0.$$

It follows from the classification theorem for surfaces (Fact \ref{fact:classification}) that $S$ is either homeomorphic to a torus (if $S$ is orientable), or a Klein bottle (if $S$ is non-orientable). Hence, by Fact \ref{fact:covering-surface}, the universal cover of the surface $S$ is the plane, $\mathbb{R}^2$.

Let $p:\mathbb{R}^2 \to S$ be a universal covering map. (Note that $(\mathbb{R}^2,S,p)$ is a normal covering space, as it is universal --- see Fact \ref{fact:covering-surface}). Let $H = p^{-1}(G')$, i.e. $H$ is the lift of the graph $G'$ (see Remark \ref{remark:covering-connection}). Then $H$ is a plane graph, and $p|V(G')$ is a covering (in the graph sense) of $G'$ by $H$, by Remark \ref{remark:covering-connection}. It follows that $H$ is 4-regular. We proceed to show that $H$ is a 4-regular quadrangulation of $\mathbb{R}^2$.

Fix a face $\sigma = (q(s_{C}))^{\circ}$ of $G'$. Then the boundary $\partial \sigma$ is a 4-cycle in $G'$. Let $\gamma_{\sigma}$ be the simple, closed curve in $S$ which traverses $\partial \sigma$ in one of the two possible directions (chosen arbitrarily). Since $\overline{\sigma}$ is homeomorphic to $s_{C}$ (via $q|s_{C}$), $\gamma_{\sigma}$ is homotopic to a constant loop in $S$. By the homotopy lifting property (Fact \ref{fact:homotopy-lifting}), any $p$-lift of $\gamma_{\sigma}$ is a simple, closed curve in $\mathbb{R}^2$. Let
$$\{\delta_{\sigma}^{(\alpha)}:\ \alpha \in I_{\sigma}\}$$
be the set of all $p$-lifts of $\gamma_{\sigma}$; then each $\delta_{\sigma}^{(\alpha)}$ is a simple, closed curve in $\mathbb{R}^2$ and a 4-cycle in $H$, and the images of the curves $\delta_{\sigma}^{(\alpha)}$ are pairwise disjoint.

Let $\Sigma$ denote the set of faces of $G'$. For each face $\sigma \in \Sigma$ and each $\alpha \in I_{\sigma}$, let $F^{(\alpha)}_{\sigma}$ denote the inside component of $\delta_{\sigma}^{(\alpha)}$, i.e. the bounded component of $\mathbb{R}^2 \setminus \Image(\delta_{\sigma}^{(\alpha)})$. Our aim is to show that $\{F^{(\alpha)}_{\sigma}:\ \sigma \in \Sigma,\ \alpha \in I_{\sigma}\}$ are precisely the faces of $H$. For this, we need the following two claims.

\begin{claim}
\label{claim:none-inside}
For each face $\sigma$ of $G'$ and each $\alpha \in I_{\sigma}$, $F^{(\alpha)}_{\sigma}$ is a face of $H$.
\end{claim}
\begin{proof}[Proof of Claim \ref{claim:none-inside}.]
It suffices to show that the inside component of $\delta^{(\alpha)}_{\sigma}$ contains no element of the point-set $[H]$. Suppose for a contradiction that $w \in [H]$ lies in the inside component of $\delta^{(\alpha)}_{\sigma}$. Since $\sigma$ is a face of $G'$, $v:=p(w)$ must lie on the outside of $\gamma_{\sigma}$. Note that
$$\left(\mathbb{R}^2 \setminus p^{-1}(v),\ S \setminus \{v\},\ p|(S\setminus \{v\})\right)$$
is a covering space (see Remark \ref{remark:subspace-covering}). Moreover, $\gamma_{\sigma}$ is homotopic to a constant loop in $S \setminus \{v\}$. It follows from the homotopy lifting property that $\delta^{(\alpha)}_{\sigma}$ is homotopic to a constant loop in $\mathbb{R}^2 \setminus p^{-1}(v)$, and therefore also in $\mathbb{R}^2 \setminus \{w\}$. But then $w$ cannot lie in the inside component of $\delta^{(\alpha)}_{\sigma}$, a contradiction.
\end{proof}

\begin{claim}
\label{claim:all-inside}
\[\mathbb{R}^2 \setminus [H] = \bigcup_{\sigma,\atop\alpha \in I_{\sigma}} F^{(\alpha)}_{\sigma}.\]
\end{claim}
\begin{proof}[Proof of Claim \ref{claim:all-inside}.]
It suffices to show that if $\sigma = (q(s_{C}))^{\circ}$ is a face of $G'$ and if $x \in \mathbb{R}^2$ with $p(x) \in \sigma$, then $x$ lies in the inside component of some $\delta_{\sigma}^{(\alpha)}$. Suppose for a contradiction that $x$ does not lie in the inside component of $\delta_{\alpha}^{(\sigma)}$, for any $\alpha$. Then for each $\alpha$, $\delta_{\sigma}^{(\alpha)}$ is a simple, closed curve in $\mathbb{R}^2 \setminus \{x\}$ with winding number $n(\delta_{\sigma}^{(\alpha)},x)=0$.

Let $y=p(x)$. Since $q|s_{C}$ is a homeomorphism from $s_{C}$ to $\overline{\sigma}$, the topology on $S$ induces the Euclidean topology on $\overline{\sigma}$. Choose two nested open discs $D \subsetneq D'$ in $S$, both of centre $y$, such that:
\begin{itemize}
\item $D' \subset \sigma$;
\item there is an open set $U \subset \mathbb{R}^2$ containing $x$, such that $p|U: U \to D'$ is a homeomorphism.
\end{itemize}
Let $\gamma$ be a simple, closed curve traversing the circle $\partial D$ in the same direction as $\gamma_{\sigma}$ traverses $\partial \sigma$. Then $\gamma$ is not homotopic to the constant loop in $D' \setminus \{y\}$, but $\gamma$ is homotopic to $\gamma_{\sigma}$ in $S \setminus \{y\}$. Let $\beta$ be the $p$-lift of $\gamma$ inside the set $U$. Then $\beta$ is a simple, closed curve in $U$. Since $p|U$ is a homeomorphism from $U$ to $D'$, and $\gamma$ is not homotopic to the constant loop in $D' \setminus \{y\}$, it follows that $\beta$ is not homotopic to the constant loop in $U \setminus \{x\}$. Since $U$ is homeomorphic to $D'$, it is simply-connected, so we have $n(\beta,x) \neq 0$, by Fact \ref{fact:winding-numbers}. On the other hand, since $\gamma$ is homotopic to $\gamma_{\sigma}$ in $S \setminus \{y\}$, it follows from the homotopy lifting property that there exists $\alpha \in I_{\sigma}$ such that $\beta$ is homotopic to $\delta_{\sigma}^{(\alpha)}$ in $\mathbb{R}^2 \setminus \{p^{-1}(y)\}$, and therefore also in $\mathbb{R}^2 \setminus \{x\}$. Hence, by Fact \ref{fact:winding-numbers} (applied with $\mathbb{R}^2$ in place of $U$), we have $n(\delta_{\sigma}^{(\alpha)},x) = n(\beta,x) \neq 0$, contradicting the fact that $n(\delta_{\sigma}^{(\alpha)},x) = 0$.
\end{proof}

Claims \ref{claim:none-inside} and \ref{claim:all-inside} immediately imply that $\{F^{(\alpha)}_{\sigma}:\ \sigma \in \Sigma,\ \alpha \in I_{\sigma}\}$ are precisely the faces of $H$, so the boundary of every face of $H$ is a 4-cycle. Hence, $H$ is a 4-regular quadrangulation of $\mathbb{R}^2$.

It follows from Lemma \ref{lemma:uniqueness} that there exists a graph isomorphism $\psi:V(\mathbb{L}^2) \to V(H)$ between $\mathbb{L}^2$ and $H$. Hence, $p \circ \psi : V(\mathbb{L}^2) \to V(G')$ is a covering of $G'$ by $\mathbb{L}^2$. Recall that $p$ is a normal covering map. This easily implies the following.

\begin{claim}
\label{claim:normal}
The covering map $p \circ \psi$ is normal (in the graph sense).
\end{claim}
\begin{proof}[Proof of Claim \ref{claim:normal}.]
Let $x,x' \in V(\mathbb{L}^2)$ with $(p \circ \psi)(x) = (p \circ \psi)(x')$. Since $p$ is a normal covering map, there exists a homeomorphism $\phi:\mathbb{R}^2 \to \mathbb{R}^2$ such that $\phi(\psi(x')) = \psi(x)$ and $p \circ \phi = p$. Since $p \circ \phi = p$, and $H = p^{-1}(G')$, we have $\phi(V(H)) = V(H)$, and for any edge $e$ of $H$, $\phi(e)$ is an edge of $H$. Hence, $\phi|V(H)$ is an automorphism of $H$. It follows that $\psi^{-1} \phi\psi:V(\mathbb{L}^2) \to V(\mathbb{L}^2)$ is an automorphism of $\mathbb{L}^2$ with
$$(p \circ \psi) \circ (\psi^{-1} \phi \psi) = (p \circ \phi) \circ \psi = p \circ \psi.$$
Hence, $\phi$ is a covering transformation of $p \circ \psi$ with $(\psi^{-1} \phi \psi)(x') = x$, proving the claim. 
\end{proof}
We have shown that $p \circ \psi$ normal covering of $G$ by $\mathbb{L}^2$, proving the theorem.
\end{proof}

\section{Algebraic structure theorems}  
In this section, we use standard techniques from topological graph theory and group theory, combined with the `topological' structure theorems of the previous two sections, to deduce Corollaries \ref{corr:torusklein2} and \ref{corr:structure-d}, which concern the `algebraic' (quotient-type) structure of graphs which have the 4-cycle-wheel property, or which are weakly 2-locally $\mathbb{L}^2$, or weakly 3-locally $\mathbb{L}^d$ (for $d \geq 3$).

\subsubsection*{The deduction of Corollary \ref{corr:torusklein2}}

We first deduce the following.

\begin{proposition}
\label{prop:quotient-wheel}
If $G$ is a finite, connected graph with the 4-cycle wheel property, then $G$ is isomorphic to $\mathbb{L}^2/\Gamma$, where $\Gamma$ is a subgroup of $\Aut(\mathbb{L}^2)$ with $|\mathbb{Z}^2/\Gamma| < \infty$ and with minimum distance at least 3.
\end{proposition}
\begin{proof}
Let $G$ be a finite, connected graph with the 4-cycle wheel property. It follows immediately from Theorem \ref{thm:cover-wheel}, Lemma \ref{lemma:free} and Lemma \ref{lemma:iso} that $G$ is isomorphic to $\mathbb{L}^2/\Gamma$, where $\Gamma$ is a subgroup of $\Aut(\mathbb{L}^2)$ which acts freely on $\mathbb{L}^2$. Clearly, we have $|\mathbb{Z}^2/\Gamma| = |V(G)| < \infty$. Observe that if $\Gamma$ has minimum displacement at most $2$, then $\mathbb{L}^2/\Gamma$ is not 4-regular, so it does not have the 4-cycle wheel property. Hence, $\Gamma$ has minimum distance at least 3.
\end{proof}

To deduce Corollary \ref{corr:torusklein2} from Proposition \ref{prop:quotient-wheel}, it remains only to classify the subgroups $\Gamma$ of $\Aut(\mathbb{L}^2)$ which have $|\mathbb{Z}^2/\Gamma| < \infty$ and minimum displacement at least 3. Note that if $\Gamma,\Gamma'$ are conjugate subgroups of $\Aut(\mathbb{L}^2)$, then $\mathbb{L}^2/\Gamma$ and $\mathbb{L}^2/\Gamma'$ are isomorphic graphs, so we need only classify subgroups of $\Aut(\mathbb{L}^2)$ up to conjugacy. This is easy to do directly, using elementary group theory, but as this approach is somewhat long-winded, we will show how to deduce the classification from some well-known group-theoretic results.

First, we need the following easy observation.
\begin{claim}
\label{claim:torsion-free2}
If $\Gamma \leq \Aut(\mathbb{L}^2)$ has minimum displacement at least 3, then $\Gamma$ is torsion-free.
\end{claim}
\begin{proof}[Proof (sketch):]
We view $\Aut(\mathbb{L}^2)$ as a subgroup of $\Isom(\mathbb{R}^2)$. The only torsion-elements of $\Isom(\mathbb{R}^2)$ are rotations and reflections, and it is easy to see that the only rotations and reflections in $\Aut(\mathbb{L}^2)$ are as follows:
\begin{itemize}
\item The identity;
\item Rotations by an angle $\theta \in \{\pi/2,\pi,3\pi/2\}$ about a point of the form $(a,b)$, where $a,b \in \mathbb{Z}$;
\item Rotations by an angle $\theta \in \{\pi/2,\pi,3\pi/2\}$ about a point of the form $(a+1/2,b+1/2)$, where $a,b \in \mathbb{Z}$;
\item Rotations by $\pi$ about a point of the form $(a+1/2,b)$ or $(a,b+1/2)$, where $a,b \in \mathbb{Z}$;
\item Reflections in lines of the form $\{x=a\}$ or $\{y = b\}$, where $a,b \in \mathbb{Z}$;
\item Reflections in lines of the form $\{x+y = a\}$ or $\{x-y = b\}$, where $a,b \in \mathbb{Z}$;
\item Reflections in lines of the form $\{x=a+1/2\}$ or $\{y = b+1/2\}$, where $a,b \in \mathbb{Z}$.
\end{itemize}
It is easy to see that each automorphism $\gamma$ in the above list has $d(\gamma,\gamma(x)) \leq 2$ for some $x \in \mathbb{Z}^2$. 
\end{proof}

We also need the $d=2$ case of the following simple fact (we shall need the $d \geq 3$ case later).
\begin{claim}
\label{claim:rank-d}
If $\Gamma \leq \Aut(\mathbb{L}^d)$ with $|\mathbb{Z}^d/\Gamma| < \infty$, then the lattice of translations of $\Gamma$ has rank $d$.
\end{claim}
\begin{proof}
Let $\Lambda_{\Gamma}$ denote the lattice of translations of $\Gamma$. Suppose $\rank(\Lambda_{\Gamma}) < d$. Let $\{v_1,\ldots,v_r\}$ be a $\mathbb{Z}$-basis for $\Lambda_{\Gamma}$; then $r < d$. Choose $w \in \mathbb{Z}^d \setminus \langle v_1,\ldots,v_r \rangle_{\mathbb{R}}$, where $\langle v_1,\ldots,v_r \rangle_{\mathbb{R}}$ denotes the subspace of $\mathbb{R}^d$ spanned by $v_1,\ldots,v_r$ over $\mathbb{R}$. We assert that for any $x \in \mathbb{Z}^d$, there are at most $2^d d!$ elements of $\{x+\lambda w:\ \lambda \in \mathbb{Z}\}:=L$ in the same $\Gamma$-orbit as $x$. Indeed, suppose otherwise. Let $S = \{\gamma \in \Gamma:\ \gamma(x) \in \{x+\lambda w:\ \lambda \in \mathbb{Z}\}\}$; then $|S| > 2^d d!$. Since $\Gamma \leq \Aut(\mathbb{L}^d) = T(\mathbb{Z}^d) \rtimes B_d$ and $|B_d|=2^d d!$ (see Fact \ref{fact:aut-ld}), by the pigeonhole principle, there exist $g \in B_d$ and two distinct translations $t_1,t_2 \in T(\mathbb{Z}^d)$ such that $t_1g, t_2g \in S$. Notice that $(t_1 g) (t_2 g)^{-1} = t_1 t_2^{-1}$ is a translation in $\Gamma \setminus \{\Id\}$. But there exist $y,z \in L$ such that $t_1 g(x)=y$ and $t_2 g(x)=z$, so $t_1 t_2^{-1}(z)=y$, so $t_1 t_2^{-1}$ fixes the set $L$, so $t_1t_2^{-1}$ is a translation by $ \mu w$ for some $\mu \in \mathbb{Z} \setminus \{0\}$, so $w \in \langle v_1,v_2,\ldots,v_r \rangle_{\mathbb{R}}$, contradicting our choice of $w$, and proving our assertion. The assertion implies that $\{\lambda w: \lambda \in \mathbb{Z}\}$ meets infinitely many $\Gamma$-orbits. Hence, $|\mathbb{Z}^d/\Gamma| = \infty$, proving the claim.
\end{proof}

Recall that we can view $\Aut(\mathbb{L}^2)$ as a discrete subgroup of $\Isom(\mathbb{R}^2)$ (see Facts \ref{fact:embedding-isometries} and \ref{fact:discrete}), and the same holds for any subgroup of $\Aut(\mathbb{L}^2)$. If $\Gamma \leq \Aut(\mathbb{L}^2)$ with $|\mathbb{Z}^2/\Gamma| < \infty$, then by Claim \ref{claim:rank-d}, the lattice of translations of $\Gamma$ has rank $2$, so $\Gamma$ is a 2-dimensional crystallographic group (see definition \ref{definition:crystallographic}). Combining this fact with Claim \ref{claim:torsion-free2} implies that if $\Gamma \leq \Aut(\mathbb{L}^2)$ with $|\mathbb{Z}^2/\Gamma| < \infty$ and with minimum displacement at least 3, then $\Gamma$ is a torsion-free 2-dimensional crystallographic group, i.e. a 2-dimensional Bieberbach group (see definition \ref{definition:bieberbach}). The classification of 2-dimensional Bieberbach groups (see for example \cite{charlap}) says the following.
\begin{proposition}
Let $\Gamma \leq \Isom(\mathbb{R}^2)$ be a 2-dimensional Bieberbach group. Then either
\begin{enumerate}
\item $\Gamma=\langle t_1,t_2\rangle$, where $t_1$ and $t_2$ are linearly independent translations, or
\item $\Gamma = \langle g,t \rangle$, where $g$ is a glide-reflection and $t$ is a translation in a direction perpendicular to the reflection-axis of $g$.
\end{enumerate}
\end{proposition}
In case (1), $\mathbb{R}^2/\Gamma$ is a (topological) torus; in case (2), $\mathbb{R}^2/\Gamma$ is a (topological) Klein bottle. This immediately implies Corollary \ref{corr:torusklein2}.

\subsubsection*{A more precise structure theorem for graphs with the 4-cycle wheel property}

We can obtain an even more precise structure theorem than Corollary \ref{corr:torusklein2}, by utilising more fully the fact that $\Gamma \leq \Aut(\mathbb{L}^2)$. The translations in $\Aut(\mathbb{L}^2)$ are of course integer translations, and the glide-reflections in $\Aut(\mathbb{L}^2)$ are of the following kinds:
\begin{itemize}
\item Glide reflections consisting of a translation $(x,y) \mapsto (x,y+a)$ followed by a reflection in the line $\{x=b\}$, where $a \in \mathbb{Z}$ and $b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x,y+a)$ followed by a reflection in the line $\{x=b+1/2\}$, where $a \in \mathbb{Z}$ and $b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a,y)$ followed by a reflection in the line $\{y=b\}$, where $a \in \mathbb{Z}$ and $b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a,y)$ followed by a reflection in the line $\{y=b+1/2\}$, where $a \in \mathbb{Z}$ and $b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a,y+a)$ followed by a reflection in the line $\{x-y=b\}$, where $a,b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a,y-a)$ followed by a reflection in the line $\{x+y=b\}$, where $a,b \in \mathbb{Z}$.
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a+1/2,y+a+1/2)$ followed by a reflection in the line $\{x-y=b+1/2\}$, where $a,b \in \mathbb{Z}$;
\item Glide reflections consisting of a translation $(x,y) \mapsto (x+a+1/2,y-a+1/2)$ followed by a reflection in the line $\{x+y=b+1/2\}$, where $a,b \in \mathbb{Z}$.
\end{itemize}

Hence, if $G$ is a finite, connected graph with the 4-cycle wheel property, then $G$ is isomorphic to $\mathbb{L}^2/\Gamma$, where either
\begin{enumerate}
\item[(1)] $\Gamma=\langle t_1,t_2\rangle$, where $t_1$ and $t_2$ are linearly independent integer translations, or
\item[(2)] $\Gamma = \langle g,t \rangle$, where $g$ is a glide-reflection with reflection-axis parallel to one of the lines $x=0$, $y=0$, $x=y$ or $x+y=0$, and $t$ is an integer translation in a direction perpendicular to the reflection-axis of $g$.
\end{enumerate}

The graphs of type (1) can be constructed by the following procedure. Start with the graph $\mathbb{L}^2$, and choose two linearly independent vectors $v_1,v_2 \in \mathbb{Z}^2$. Identify the vertex $x$ with the vertices $x+v_1,x+v_2$, for all vertices $x \in \mathbb{Z}^2$, and identify the edge $\{x,y\}$ with the edges $\{x+v_1,y+v_1\}$ and $\{x+v_2,y+v_2\}$, for all edges $\{x,y\} \in E(\mathbb{L}^2)$.

Here is an example with $v_1 = (9,3)$ and $v_2 = (3,6)$. Note that vertices coloured the same colour are identified.

\begin{center}
\begin{tikzpicture}
\draw[step=0.5cm,color=gray] (0,0) grid (6,4.5);
\draw (0,0) -- (4.5,1.5) -- (6,4.5) -- (1.5,3) -- (0,0);
\path[->]
(0,0) edge (0.75,1.5)
(4.5,1.5) edge (5.25,3);
\path[->]
(1.5,3) edge (3.75,3.75)
(3.75,3.75) edge (3.9,3.8)
(0,0) edge (2.25,0.75)
(2.25,0.75) edge (2.4,0.8);
\coordinate (a) at (0.5,1);
\coordinate (b) at (5,2.5);
\coordinate (c) at (1.5,0.5);
\coordinate (d) at (3,3.5);
\fill (a) circle (2pt);
\fill (b) circle (2pt);
\fill[red] (c) circle (2pt);
\fill[red] (d) circle (2pt);
\node at (3,5) {Figure 0.0};
\end{tikzpicture}
\end{center}

Observe that this class of graphs includes the familiar `discrete torus' graph $C_k \times C_l$
(obtained by taking the $k \times l$ grid $\mathbb{L}^2[\{0,1,\ldots,k\} \times \{0,1,\ldots,l\}]$, and identifying opposite sides), but also includes graphs which are not of this form, where the `fundamental domains' in $\mathbb{R}^2$ are non-rectangular. We therefore call the graphs of type (1) `\emph{generalised discrete torus graphs}'.

Similarly, the graphs of type (2) can be constructed by one of the following two procedures.
\begin{description}
\item[Procedure I:] Choose a pair of integers $(k,l) \in \mathbb{N}^2$. Choose an axis-parallel rectangle $ABCDA :=R$ in $\mathbb{R}^2$, with $\vec{AD} = \vec{BC} = (0,l)$ and $\vec{AB} = \vec{DC} = (k,0)$. Produce a quotient space $K$ (homeomorphic to a Klein bottle) by identifying the sides $AD$ and $BC$ in the `same' direction (starting with $A$ and $B$, and ending with $D$ and $C$) and identifying the sides $AB$ and $DC$ in `opposite' directions (starting with $A$ and $C$, and ending with $B$ and $D$). Let $q:R \to K$ denote the quotient map. Let $\pi: \mathbb{R}^2 \to K$ denote the standard covering map from $\mathbb{R}^2$ to $K$, produced by tiling $\mathbb{R}^2$ with translates of the rectangle $R$ and extending $q$ from $R$ to $\mathbb{R}^2$ in the natural way. Let $G$ be the graph with $V(G)=\pi(\mathbb{Z}^2)$, where $vw \in E(G)$ iff there exist $x \in \pi^{-1}(v)$ and $y \in \pi^{-1}(w)$ with $xy \in E(\mathbb{L}^2)$.
\item[Procedure II:] Choose a pair of integers $(k,l) \in \mathbb{N}^2$. Choose a rectangle $ABCDA := R$ in $\mathbb{R}^2$ such that $\vec{AD} = \vec{BC} = (k/2,k/2)$ and $\vec{AB} = \vec{DC} = (l,-l)$. (Equivalently, rotating through $\pi/2$, we may choose $\vec{AD} = \vec{BC} = (-k/2,k/2)$ and $\vec{AB} = \vec{DC} = (l,l)$.) Produce a quotient space $K$ (homeomorphic to a Klein bottle) in exactly the same way as in Procedure I. Let $\pi: \mathbb{R}^2 \to K$ denote the standard covering map. Let $G$ be the graph with $V(G)=\pi(\mathbb{Z}^2)$, where $vw \in E(G)$ iff there exist $x \in \pi^{-1}(v)$ and $y \in \pi^{-1}(w)$ with $xy \in E(\mathbb{L}^2)$.
\end{description}
Here are three examples to illustrate Procedure I. Note that vertices coloured the same colour are identified, and the dotted green line denotes the reflection axis of a glide reflection (see the discussion on page \pageref{page:glide}).
\newline

\begin{tikzpicture}
\draw[step=0.5cm,color=gray] (-2,-2) grid (2.5,3);
\draw(-1.25,-1.5) -- (1.75,-1.5);
\draw(-1.25,-1.5) -- (-1.25,2.5);
\draw(1.75,-1.5) -- (1.75,2.5);
\draw(-1.25,2.5) -- (1.75,2.5);
\draw[dashed,very thick, color=green] (0.25,-2) -- (0.25,3);f
\node at (0.25,3.5) {Figure 1.0};
\path[->]
(-1.25,-1.5) edge (-1.25,0.5)
(1.75,-1.5) edge (1.75,0.5)
(-1.25,-1.5) edge (0.25,-1.5)
(0.25,-1.5) edge (0.3,-1.5)
(1.75,2.5) edge (0.3,2.5)
(0.3,2.5) edge (0.25,2.5);
\coordinate (e) at (1.5,-1.5);
\coordinate (f) at (-1,2.5);
\coordinate (g) at (-1.5,-0.5);
\coordinate (h) at (-1,-0.5);
\coordinate (q) at (1.5,-0.5);
\coordinate (r) at (2,-0.5);
\node at (-1.25,-1.5) [below] {$A$};
\node at (1.75,-1.5) [below] {$B$};
\node at (-1.25,2.5) [above] {$D$};
\node at (1.75,2.5) [above] {$C$};
\fill (e) circle (2pt);
\fill (f) circle (2pt);
\fill[red] (g) circle (2pt);
\fill[blue] (h) circle (2pt);
\fill[red] (q) circle (2pt);
\fill[blue] (r) circle (2pt);
\draw[step=0.5cm,color=gray] (4,-2) grid (8,3);
\draw[color=gray] (4,-2) -- (4,3);
\draw(4.75,-1.5) -- (4.75,2.5) -- (7.25,2.5) -- (7.25,-1.5) -- (4.75,-1.5);
\path[->]
(4.75,-1.5) edge (4.75,0.5)
(7.25,-1.5) edge (7.25,0.5)
(4.75,-1.5) edge (6,-1.5)
(6,-1.5) edge (6.05,-1.5)
(7.25,2.5) edge (6.05,2.5)
(6.05,2.5) edge (6,2.5);
\draw[dashed,very thick,color=green] (6,-2) -- (6,3);
\node at (6,3.5) {Figure 1.1};
\coordinate (x) at (7,-1.5);
\coordinate (y) at (5,2.5);
\coordinate (z) at (7,-0.5);
\coordinate (u) at (7.5,-0.5);
\coordinate (v) at (4.5,-0.5);
\coordinate (w) at (5,-0.5);
\node at (4.75,-1.5) [below] {$A$};
\node at (7.25,-1.5) [below] {$B$};
\node at (4.75,2.5) [above] {$D$};
\node at (7.25,2.5) [above] {$C$};
\fill (x) circle (2pt);
\fill (y) circle (2pt);
\fill[red] (z) circle (2pt);
\fill[blue] (u) circle (2pt);
\fill[red] (v) circle (2pt);
\fill[blue] (w) circle (2pt);
\end{tikzpicture}
\newline

\begin{tikzpicture}
\draw[step=0.5cm,color=gray] (-2,-2) grid (2,2.5);
\draw(-1.5,-1.5) -- (1.5,-1.5);
\draw(-1.5,-1.5) -- (-1.5,2);
\draw(1.5,-1.5) -- (1.5,2);
\draw(-1.5,2) -- (1.5,2);
\path[->]
(-1.5,-1.5) edge (-1.5,0.25)
(1.5,-1.5) edge (1.5,0.25)
(-1.5,-1.5) edge (0,-1.5)
(0,-1.5) edge (0.05,-1.5)
(1.5,2) edge (0.05,2)
(0.05,2) edge (0,2);
\coordinate (e) at (1,-1.5);
\coordinate (f) at (-1,2);
\coordinate (g) at (-1.5,-0.5);
\coordinate (h) at (1.5,-0.5);
\node at (-1.5,-1.5) [below left] {$A$};
\node at (1.5,-1.5) [below right] {$B$};
\node at (-1.5,2) [above left] {$D$};
\node at (1.5,2) [above right] {$C$};
\fill (e) circle (2pt);
\fill (f) circle (2pt);
\fill[red] (g) circle (2pt);
\fill[red] (h) circle (2pt);
\draw[dashed,very thick,color=green] (0,-2) -- (0,2.5);
\node at (0,3) {Figure 1.2};
\end{tikzpicture}
\newline

Here is an example to illustrate Procedure II.
\newline

\begin{tikzpicture}
\draw[step=0.5cm,color=gray] (-1,-2) grid (3.5,3);
\draw (-0.875,0.875) -- (0.875,2.625);
\draw (-0.875,0.875) -- (1.625,-1.625);
\draw (1.625,-1.625) -- (3.375,0.125);
\draw (3.375,0.125) -- (0.875,2.625);
\draw[dashed,very thick, color=green] (-1,-1.75) -- (3.5,2.75);
\node at (1.25,3.5) {Figure 2.0};
\path[->]
(-0.875,0.875) edge (0,1.75)
(1.625,-1.625) edge (2.5,-0.75)
(-0.875,0.875) edge (0.375,-0.375)
(0.375,-0.375) edge (0.425,-0.425)
(3.375,0.125) edge (2.125,1.375)
(2.125,1.375) edge (2.075,1.425);
\coordinate (e) at (0,1.5);
\coordinate (f) at (2.5,-1);
\coordinate (g) at (-0.5,1.5);
\coordinate (h) at (2,-1);
\coordinate (q) at (-0.5,0.5);
\coordinate (r) at (3,0.5);
\fill[blue] (e) circle (2pt);
\fill[blue] (f) circle (2pt);
\fill[red] (g) circle (2pt);
\fill[red] (h) circle (2pt);
\fill (q) circle (2pt);
\fill (r) circle (2pt);
\node at (-0.875,0.875) [left] {$A$};
\node at (1.625,-1.625) [below] {$B$};
\node at (0.875,2.625) [above] {$D$};
\node at (3.375,0.125) [right] {$C$};
\end{tikzpicture}
\newline

We call the graphs of type (2) `\emph{discrete Klein bottle graphs}'. Notice that a discrete Klein bottle graph has a fundamental domain ($R$, in the above definitions) which is rectangular, and either parallel to the coordinate axes or at an angle of $\pi/4$. By contrast, a generalised discrete torus graph may have no rectangular fundamental domain; rather, it has a fundamental domain which is a parallelogram, and which may be at any of infinitely many different angles to the coordinate axes.

We can now state our most precise structure theorem for graphs with the 4-cycle wheel property, which follows immediately from the above argument.

\begin{theorem}
\label{thm:structure-2}
Let $G$ be a connected, finite graph with the 4-cycle wheel property. Then $G$ is either a generalised discrete torus graph, or a discrete Klein bottle graph. 
\end{theorem}

\subsubsection*{Connections with prior results}

Theorem \ref{thm:structure-2} gives an alternative, `algebraic' restatement (and a new proof) of Theorem 1 in \cite{noy}, the structure theorem of M\'arquez, de Mier, Noy and Revuelta for locally-grid graphs, and also of Theorem 4.1 in \cite{thomassen-torus}, the structure theorem of Thomassen for graphs with the 4-cycle wheel property. Before stating these two theorems, we recall some definitions from \cite{noy}.

\begin{definition}
Let $G$ be a graph. We say that $G$ is a {\em locally-grid graph} if it is 4-regular, and for every vertex $v \in V(G)$, there exists an ordering $w_1,w_2,w_3,w_4$ of the elements of $\Gamma(v)$, and four other distinct vertices $z_1,z_2,z_3,z_4 \in V(G)$ such that, taking the indices modulo 4, we have $\Gamma(w_i) \cap \Gamma(w_{i+1}) = \{v,z_i\}$ and $\Gamma(w_i) \cap \Gamma(w_{i+2}) = \{v\}$ for all $i$. Moreover, there are no adjacencies among $\{v,w_1,w_2,w_3,w_4,z_1,z_2,z_3,z_4\}$ other than those required by the above conditions.
\end{definition}

Note that a locally-grid graph is weakly $2$-locally $\mathbb{L}^2$, but the converse does not hold. Indeed, the generalised discrete torus graph constructed by taking the quotient of $\mathbb{L}^2$ by the lattice generated by $(3,2)$ and $(0,6)$, is weakly $2$-locally $\mathbb{L}^2$, but is not a locally-grid graph. Note also that a graph which is 2-locally $\mathbb{L}^2$ is a locally-grid graph; on the other hand, the discrete torus $C_5 \times C_5$ is a locally-grid graph, but is not $2$-locally $\mathbb{L}^2$.

If $p,q \in \mathbb{N}$ with $p,q \geq 2$, then following \cite{noy}, we define the {\em grid graph} $H_{p,q}$ to be the induced subgraph $\mathbb{L}^2[\{0,1,\ldots,p-1\} \times \{0,1,\ldots,q-1\}]$, i.e. the graph with vertex-set $\{0,1,\ldots,p-1\} \times \{0,1,\ldots,q-1\}$, where two vertices are joined if and only if they have Euclidean distance 1 apart. 

If $p,q \in \mathbb{N}$ with $p \geq 3$ and $\delta \in \{0,1,2,\ldots,\lfloor p/2 \rfloor\}$, the {\em torus graph} $T_{p,q}^{\delta}$ is the graph with vertex-set $V(H_{p,q}) = \{0,1,\ldots,p-1\} \times \{0,1,\ldots,q-1\}$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(i,0),(i+\delta,q-1)\}:\ 0 \leq i \leq p-1\}\\
& \cup\{\{(0,j),(p-1,j)\}: 0 \leq j \leq q-1\}.\end{align*}

If $p,q \geq 3$ are integers with $p$ even, the {\em Klein bottle graph of type 0} $K_{p,q}^{0}$ is the graph with vertex-set $V(H_{p,q})$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(0,j),(p-1,j)\}:\ 0 \leq j \leq q-1\}\\
& \cup\{\{(i,0),(p-i-1,q-1)\}: 0 \leq i \leq p-1\}.\end{align*}

If $p,q \geq 3$ are integers with $p$ odd, the {\em Klein bottle graph of type 1} $K_{p,q}^{1}$ is the graph with vertex-set $V(H_{p,q})$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(0,j),(p-1,j)\}:\ 0 \leq j \leq q-1\}\\
& \cup\{\{(i,0),(p-i-1,q-1)\}: 0 \leq i \leq p-1\}.\end{align*}

If $p,q \geq 3$ are integers with $p$ even, the {\em Klein bottle graph of type 2} $K_{p,q}^{2}$ is the graph with vertex-set $V(H_{p,q})$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(0,j),(p-1,j)\}:\ 0 \leq j \leq q-1\}\\
& \cup\{\{(i,0),(p-i,q-1)\}: 0 \leq i \leq p-1\}.\end{align*}

If $p$ and $q$ are integers with $p,q \geq 3$, the {\em strange graph} $S_{p,q}$ is defined as follows. If $p \leq q$, then $S_{p,q}$ is the graph with vertex-set $V(H_{p,q})$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(i,0),(p-1,q-p+i)\}:\ 0 \leq i \leq p-1\}\\
& \cup\{\{(0,j),(j,q-1)\}: 0 \leq j \leq p-1\}\\
& \cup \{ \{(0,j),(p-1,i-p)\}: p \leq j \leq q-1\} .\end{align*}
If $p \geq q$, then $S_{p,q}$ is the graph with vertex-set $V(H_{p,q})$, and edge-set
\begin{align*} E(H_{p,q}) & \cup \{\{(i,0),(0,q-1-i)\}:\ 0 \leq i \leq q-1\}\\
& \cup\{\{(p-1-i,q-1),(p-1,i)\}: 0 \leq i \leq q-1\}\\
& \cup \{ \{(i,q-1),(i+q,0)\}: 0 \leq i \leq p-q-1\} .\end{align*}

We recall the following.

\begin{theorem}[M\'arquez, de Mier, Noy, Revuelta, Theorem 1 in \cite{noy}]
\label{thm:noy}
Let $G$ be an $n$-vertex, locally-grid graph. Then one of the following holds.
\begin{itemize}
\item $G \cong T_{p,q}^{\delta}$, where $pq=n$ and $0 \leq \delta \leq p/2$.
\item $G \cong K_{p,q}^{t}$, where $pq=n$ and $t \in \{0,1,2\}$.
\item $G \cong S_{p,q}$, where $pq=n$.
\end{itemize}
\end{theorem}
(For brevity, we have stated this theorem without some extra conditions on $p,q$ and $\delta$ which are added in \cite{noy}, corresponding to the fact that $p$ and $q$ must be large enough to ensure that the locally-grid condition holds.)

\begin{theorem}[Thomassen, Theorem 4.1 in \cite{thomassen-torus}]
\label{thm:thomassen}
The conclusion of Theorem \ref{thm:noy} also holds if $G$ is an $n$-vertex graph with the 4-cycle wheel property.
\end{theorem}

Note that, as outlined in \cite{noy}, the statement of Theorem 4.1 in \cite{thomassen-torus} omits the case of $S_{p,q}$ with $p > q$, due to a small oversight in the proof.

It is easy to see that the torus graph $T_{p,q}^{\delta}$ is precisely the quotient of $\mathbb{L}^2$ by the sublattice generated by the vectors
$$v_1 = (p,0),\ v_2 = (\delta,q)$$
so it is a `generalised discrete torus graph' (in our sense). Similarly, it is easy to see that the Klein bottle graphs of types 0, 1 and 2 are `discrete Klein bottle graphs' constructible by Procedure I above. Indeed, for $K_{p,q}^{0}$ and $K_{p,q}^{1}$, we may take the rectangle $R$ to have vertices $A = (-1/2,0),\ B= (p-1/2,0),\ C = (p-1/2,q),\ D = (-1/2,q)$. For $K_{p,q}^{2}$, we may take $A = (0,0),\ B = (p,0),\ C = (p,q),\ D = (0,q)$. Note that Figure 1.0 shows $K_{6,8}^{0}$, Figure 1.1 shows $K_{5,8}^{1}$, and Figure 1.2 shows $K_{6,7}^{2}$. 

However, for the `strange' graphs $S_{p,q}$, it is not immediately obvious that they can even be embedded into the Klein bottle. Such embeddings are shown for $(p,q) = (5,7)$ and $(p,q) = (7,5)$ in \cite{noy}; it is easy to see how to generalise these embeddings to the case of arbitrary $p,q$. In fact, though, the `strange' graphs are precisely the discrete Klein bottle graphs constructible by Procedure II. Indeed, if $p \leq q$ we may obtain $S_{p,q}$ from Procedure II by taking $k=q$ and $l = p$, and taking $R$ to be the rectangle bounded by the lines $x+y=0$, $x+y = q$, $y=x+q/2$ and $y = x-2p+q/2$, with $A$ and $B$ lying on the line $x+y=0$. Equivalently, $S_{p,q}$ is the quotient of $\mathbb{L}^2$ by the subgroup $\Gamma = \langle g,t \rangle$, where
$$t: (x,y) \mapsto (x,y) + (p,-p)$$
is a translation, and
$$g: (x,y) \mapsto (y+p,x+q-p)$$
is a glide-reflection, consisting of the translation $(x,y) \mapsto (x,y)+(q/2,q/2)$, followed by reflection in the line $y = x-p+q/2$. Figure 2.0 illustrates this with $(p,q) = (5,7)$. The dotted green line is the reflection axis of the glide-reflection $g$. \label{page:glide}

Similarly, if $p \geq q$, we may obtain $S_{p,q}$ from Procedure II by taking $k=q$ and $l = p$, and taking $R$ to be the rectangle bounded by the lines $y=x,\ y = x-q$, $x+y = -p+q/2-1$ and $x+y = p+q/2-1$, with $A$ and $B$ on the line $y=x-q$. Equivalently, $S_{p,q}$ is the quotient of $\mathbb{L}^2$ by the subgroup $\Gamma = \langle g,t \rangle$, where
$$t: (x,y) \mapsto (x,y) + (p,p)$$
is a translation, and
$$g:(x,y) \mapsto (-y-1,q-1-x)$$
is a glide-reflection, consisting of the translation $(x,y) \mapsto (x,y)+(-q/2,q/2)$, followed by reflection in the line $x+y = q/2-1$.

Hence, our methods automatically yield a natural representation of the `strange' graphs as quotients of $\mathbb{L}^2$; so perhaps they are not so `strange' after all!

\subsubsection*{The deduction of Corollary \ref{corr:structure-d}}
We now turn our attention to the case of general $d$. We will need the following easy lemma.

\begin{lemma}
\label{lemma:min-dist-r}
Let $d,r \in \mathbb{N}$, and let $\Gamma \leq \Aut(\mathbb{L}^d)$. Let $D(\Gamma)$ denote the minimum displacement of $\Gamma$. Then
\begin{itemize}
\item[(i)] $\mathbb{L}^d/\Gamma$ is $r$-locally $\mathbb{L}^d$ if and only if $D(\Gamma) \geq 2r+2$.
\item[(ii)] $\mathbb{L}^d/\Gamma$ is weakly $r$-locally $\mathbb{L}^d$ if and only if $D(\Gamma) \geq 2r+1$.
\end{itemize}
\end{lemma}
 
\begin{proof}
(i) Suppose $\Gamma \leq \Aut(\mathbb{L}^d)$ has $D(\Gamma) \geq 2r+2$. Let $x \in V(\mathbb{L}^d)$. Then it is easy to check that the orbit map $x \mapsto \Orb_{\Gamma}(x)$ is a graph isomorphism from $\Link_r(x,\mathbb{L}^d)$ to $\Link_{r}(\Orb(x),\mathbb{L}^d/\Gamma)$ which maps $x$ to $\Orb(x)$, so $\mathbb{L}^d/\Gamma$ is $r$-locally $\mathbb{L}^d$.

On the other hand, suppose $\Gamma \leq \Aut(\mathbb{L}^d)$ has $D(\Gamma) \leq 2r+1$. If $D(\Gamma) = 2r+1$, then there exist $y,z \in V(\mathbb{L}^d)$ and $\gamma \in \Gamma$ with $d_{\mathbb{L}^d}(y,z) = 2r+1$ and $\gamma(y)=z$, so $\Orb(y)=\Orb(z)$. Let $(y,x_1,x_2,\ldots,x_{2r},z)$ be a geodesic in $\mathbb{L}^d$ from $y$ to $z$; then
$$\Orb(y) \Orb(x_1) \Orb(x_2) \ldots \Orb(x_{2r})\Orb(y)$$
is a cycle in $\mathbb{L}^d/\Gamma$ of length $2r+1$, so $\mathbb{L}^d/\Gamma$ is not $r$-locally $\mathbb{L}^d$. We may assume henceforth that $D(\Gamma) \leq 2r$.

Now note that if $\{\Orb(x),\Orb(y)\} \in E(\mathbb{L}^d/\Gamma)$, then there exists $z \in \Orb(y)$ such that $\{x,z\} \in E(\mathbb{L}^d)$. Indeed, if $\{\Orb(x),\Orb(y)\} \in E(\mathbb{L}^d/\Gamma)$, then there exist $\gamma,\gamma' \in \Gamma$ such that $\{\gamma(x),\gamma'(y)\} \in E(\mathbb{L}^d)$, and therefore $\{x,\gamma^{-1}\gamma'(y)\} \in E(\mathbb{L}^d)$, so we may take $z = \gamma^{-1}\gamma'(y)$. Similarly, if $(\Orb(x_0),\Orb(x_1),\Orb(x_2),\ldots,\Orb(x_l))$ is a path in $\mathbb{L}^d/\Gamma$, then there exist $z_i \in \Orb(x_i)$ for each $i \in [l]$ such that $(x_0,z_1,z_2,\ldots,z_l)$ is a path in $\mathbb{L}^d$. It follows that the number of vertices of $\mathbb{L}^d/\Gamma$ of distance at most $r$ from $\Orb(x)$ is precisely the number of $\Gamma$-orbits of $V(\mathbb{L}^d)$ intersecting the ball $B_r(x,\mathbb{L}^d)$.

Since $D(\Gamma) \leq 2r$, there exist $y,z \in V(\mathbb{L}^d)$ and $\gamma \in \Gamma$ such that $d_{\mathbb{L}^d}(y,z) \leq 2r$ and $\gamma(y)=z$, so $\Orb(y)=\Orb(z)$. Choose $x \in V(\mathbb{L}^d)$ such that $y,z \in B_r(x,\mathbb{L}^d)$. Then $\Orb(y)$ intersects $B_r(x,\mathbb{L}^d)$ in at least two vertices ($y$ and $z$), so
\begin{align*} |B_{r}(\Orb(x),\mathbb{L}^d/\Gamma)| & = \textrm{no. of }\Gamma\textrm{-orbits of }V(\mathbb{L}^d)\textrm{ intersecting }B_r(x,\mathbb{L}^d)\\
&< |B_r(x,\mathbb{L}^d)|.\end{align*}
It follows that $\mathbb{L}^d/\Gamma$ is not $r$-locally $\mathbb{L}^d$.

(ii) Suppose $\Gamma \leq \Aut(\mathbb{L}^d)$ has $D(\Gamma) \geq 2r+1$. Let $x \in V(\mathbb{L}^d)$. It is easy to check that the orbit map $x \mapsto \Orb_{\Gamma}(x)$ is a bijective graph homomorphism from $\Link_r(x,\mathbb{L}^d)$ to $\Link_{r}(\Orb(x),\mathbb{L}^d/\Gamma)$ which maps $x$ to $\Orb(x)$. Hence, by Observation \ref{obs:bijective-homomorphism}, $\mathbb{L}^d/\Gamma$ is weakly $r$-locally $\mathbb{L}^d$.

On the other hand, suppose $\Gamma \leq \Aut(\mathbb{L}^d)$ has $D(\Gamma) \leq 2r$. Then, by the same argument as in part (i),
\begin{align*} |B_{r}(\Orb(x),\mathbb{L}^d/\Gamma)| & = \textrm{no. of }\Gamma\textrm{-orbits of }V(\mathbb{L}^d)\textrm{ intersecting }B_r(x,\mathbb{L}^d)\\
&< |B_r(x,\mathbb{L}^d)|,\end{align*}
so $\mathbb{L}^d/\Gamma$ is not weakly $r$-locally $\mathbb{L}^d$.
\end{proof}

We can now deduce the following analogue of Proposition \ref{prop:quotient-wheel}.
\begin{proposition}
\label{prop:quotient-d}
Let $d \in \mathbb{N}$ with $d \geq 2$.
\begin{enumerate}
\item[(i)] If $G$ is a finite, connected graph which is weakly 3-locally $\mathbb{L}^d$, then $G$ is isomorphic to $\mathbb{L}^d/\Gamma$, where $\Gamma \leq \Aut(\mathbb{L}^d)$ with $|\mathbb{Z}^d/\Gamma| < \infty$ and with $D(\Gamma) \geq 7$.
\item[(ii)] If $G$ is a finite, connected graph which is 3-locally $\mathbb{L}^d$, then $G$ is isomorphic to $\mathbb{L}^d/\Gamma$, where $\Gamma \leq \Aut(\mathbb{L}^d)$ with $|\mathbb{Z}^d/\Gamma| < \infty$ and with $D(\Gamma) \geq 8$.
\end{enumerate}
\end{proposition}
\begin{proof}
Let $G$ be a finite, connected graph which is weakly 3-locally $\mathbb{L}^d$. It follows immediately from Theorem \ref{thm:cover-d}, Lemma \ref{lemma:free} and Lemma \ref{lemma:iso} that $G$ is isomorphic to $\mathbb{L}^d/\Gamma$, where $\Gamma$ is a subgroup of $\Aut(\mathbb{L}^d)$ which acts freely on $\mathbb{L}^d$. Clearly, we have $|\mathbb{Z}^d/\Gamma| = |V(G)| < \infty$. By part (ii) of Lemma \ref{lemma:min-dist-r} applied with $r=3$, we have $D(\Gamma) \geq 7$. If in addition, $G$ is 3-locally $\mathbb{L}^d$, then by part (i) of the lemma, we have $D(\Gamma) \geq 8$.
\end{proof}

To deduce Corollary \ref{corr:structure-d} from Proposition \ref{prop:quotient-d}, note that, as in the $d=2$ case, $\Aut(\mathbb{L}^d)$ can be viewed as a discrete subgroup of $\Isom(\mathbb{R}^d)$, and the same holds for any subgroup $\Gamma \leq \Aut(\mathbb{L}^d)$. If $\Gamma \leq \Aut(\mathbb{L}^d)$ with $|\mathbb{Z}^d/\Gamma|< \infty$, then by Claim \ref{claim:rank-d}, the lattice of translations $T_{\Gamma}$ of $\Gamma$ has rank $d$, and therefore $\Gamma$ is a $d$-dimensional crystallographic group. Hence, each quotient graph $\mathbb{L}^d/\Gamma$ which arises in Proposition \ref{prop:quotient-d}, can be viewed as the quotient lattice of $\mathbb{L}^d$ inside the orbit space $\mathbb{R}^d/\Gamma$. Since $T_{\Gamma}$ has rank $d$, $\mathbb{R}^d/\Gamma$ is compact. If $\Gamma$ is a \textbf{torsion-free} $d$-dimensional crystallographic group (a.k.a. a $d$-dimensional Bieberbach group), then $\mathbb{R}^d/\Gamma$ is a topological manifold (see Fact \ref{fact:proper-orbifold}). However, the group $\Gamma$ arising in Proposition \ref{prop:quotient-d} need not be torsion-free, and we will see below that $\mathbb{R}^d/\Gamma$ need not be a topological manifold. However, by Fact \ref{fact:proper-orbifold}, $\mathbb{R}^d/\Gamma$ can be given the structure of a $d$-dimensional topological orbifold.

\begin{remark}
\label{remark:not-manifold}
To see that we cannot replace `orbifold' by `topological manifold' in Corollary \ref{corr:structure-d}, consider the group
$$\Gamma = \langle \{(x \mapsto x+2de_i):\ i \in [d]\} \cup \{(x \mapsto (1,1,\ldots,1)-x)\}\rangle;$$
this contains an element of order 2, so is not torsion-free. It has $|\mathbb{Z}^d/\Gamma| < \infty$ and has minimum displacement $d$, so by Lemma \ref{lemma:min-dist-r}, $\mathbb{L}^d/\Gamma$ is weakly 3-locally $\mathbb{L}^d$ if $d \geq 7$, and 3-locally-$\mathbb{L}^d$ if $d \geq 8$. However, for each $d \geq 3$, $\mathbb{R}^d/\Gamma$ is not a topological manifold. This follows, for example, from the fact that a small metric ball around the point $[(1/2,1/2,\ldots,1/2)]$ has topological boundary homeomorphic to $(d-1)$-dimensional projective space $\mathbb{RP}^{d-1}$, whereas it is known that no subset of $\mathbb{R}^{d}$ is homeomorphic to $\mathbb{RP}^{d-1}$ if $d \geq 3$. (See \cite{hatcher} Chapter 3, p. 256 for a proof of this in the case of odd $d$, and \cite{thom} for a proof for all $d \geq 3$.)
\end{remark}

\section{Conclusion and related problems}
Theorem \ref{thm:cover-d} states that a connected graph $G$ which is weakly 3-locally $\mathbb{L}^d$ is normally covered by $\mathbb{L}^d$. Example \ref{example:Ld} shows that for each $d \geq 3$, the hypothesis of Theorem \ref{thm:cover-d} cannot be weakened to $G$ being 2-locally $\mathbb{L}^d$. Nevertheless, Example \ref{example:Ld} is still `highly structured', and we are not aware of any essentially different alternative constructions. It would be interesting to obtain a (weaker) structure theorem for graphs which are $2$-locally $\mathbb{L}^d$ (for each $d \geq 3$), and to do the same for graphs which are weakly 2-locally $\mathbb{L}^d$ (for each $d \geq 3$).

Our results imply that if $r \geq r^{*}(d)$, then a connected graph which is $r$-locally $\mathbb{L}^d$ is covered by $\mathbb{L}^d$, where
$$r^{*}(d) := \begin{cases} 2 & \textrm{if } d = 2;\\ 3 & \textrm{if } d \geq 3.\end{cases}$$
 Benjamini and Georgakopoulos conjectured the following generalisation of this fact.

\begin{conjecture}[Benjamini, Georgakopoulos]
\label{conj:finitely-presented}
Let $\Gamma$ be a finitely presented group, and let $F$ be a connected, locally finite Cayley graph of $\Gamma$. Then there exists $r \in \mathbb{N}$ such that if $G$ is a graph which is $r$-locally $F$, then $F$ covers $G$.
\end{conjecture}

(Note that this conjecture appeared in \cite{coarse-geometry} without the assumption of $\Gamma$ being finitely presented. It is easy to see that the conjecture is false without this assumption, however, and the conjecture was afterwards amended to the above.)

In \cite{dST}, de la Salle and Tessera disprove Conjecture \ref{conj:finitely-presented}; they also prove several positive results, among which is the following. If $F$ is a graph and $k \in \mathbb{N}$ with $k \geq 2$, we let $P_k(F)$ denote the polygonal $2$-complex whose 1-skeleton is $F$, and whose $2$-cells are the cycles of length at most $k$ in $F$. Following \cite{dST}, we say that $F$ is {\em simply connected at level $k$} if $P_k(F)$ is simply connected, and we say that $F$ is {\em large-scale simply connected} if there exists $k \geq 2$ such that $F$ is simply connected at level $k$.
\begin{theorem}[De La Salle, Tessera]
\label{thm:positive}
Let $F$ be a connected, locally finite graph which is large-scale simply connected, and which has $|V(F)/\Aut(F)| < \infty$ and $|\Stab_{\Aut(F)}(v)| < \infty$ for all $v \in V(F)$. Then there exists $r = r(F) \in \mathbb{N}$ such that if $G$ is a graph which is $r$-locally $F$, then $F$ covers $G$.
\end{theorem}

Since $\mathbb{L}^d$ satisfies the hypotheses of Theorem \ref{thm:positive} for any $d \in \mathbb{N}$, the $\mathbb{L}^d$-case of Theorem \ref{thm:positive} implies a weakened version of Theorem \ref{thm:cover-d}.

\begin{comment} (Although the theorem is stated without explicit bounds on $r(F)$, the proof in \cite{dST} can be easily adapted to show that for any integer $d \geq 2$, if $G$ is a connected graph which is 5-locally $\mathbb{L}^d$, then $G$ is covered by $\mathbb{L}^d$.)
\end{comment}

It would be interesting to determine more precisely the class of graphs $F$ for which the conclusion of Conjecture \ref{conj:finitely-presented} holds; note that this class contains $T_d$, the infinite $d$-regular tree, which (for $d \geq 3$) does not satisfy the hypotheses of Theorem \ref{thm:positive}, as $\Aut(T_d)$ has infinite vertex-stabilizers. It would also be of interest to obtain good quantitative bounds on $r(F)$ for graphs $F$ in various classes (such as Cayley graphs on nilpotent groups of step $k$).

\section{Appendix: Two proofs of Lemma \ref{lemma:uniqueness}.}
The following proof (which uses covering spaces) is due to \'E. Colin de Verdi\`ere \cite{colin-personal}.
\begin{proof}[First proof of Lemma \ref{lemma:uniqueness}]
Let $G$ be a 4-regular quadrangulation of $\mathbb{R}^2$. Choose any vertex $v_{(0,0)} \in G$, and choose one of the four faces incident to $v_{(0,0)}$, say $v_{(0,0)} v_{(1,0)} v_{(1,1)} v_{(0,1)} v_{(0,0)}$. We define a map $\phi:\mathbb{R}^2 \to \mathbb{R}^2$ by a recursive procedure, as follows. First define $\phi(i,j) = v_{(i,j)}$ for each $(i,j) \in \{0,1\}^2$. Then extend $\phi$ to a homeomorphism from the boundary of the unit square $S_1$ with corners $(0,0),(1,0),(1,1),(0,1)$ to the face-cycle $v_{(0,0)} v_{(1,0)} v_{(1,1)} v_{(0,1)} v_{(0,0)}$ of $G$. Now extend $\phi$ to a homeomorphism from the whole of $S_1$ to the whole closed face $v_{(0,0)} v_{(1,0)} v_{(1,1)} v_{(0,1)} v_{(0,0)}$.

Let $\mathcal{S}$ denote the set of all closed faces of $\mathbb{L}^2$ (that is, $\mathcal{S}$ is the set of unit squares whose corners have integer coordinates). Define an ordering $\prec$ on $\mathcal{S}$ such that
\begin{itemize}
\item For each $r \in \mathbb{N}$, there is an initial segment of $\prec$ whose union is the $\ell^{\infty}$-ball
$$B_{r} : = \{x \in \mathbb{R}^2:\ |x_1|,|x_2| \leq r\};$$
\item $S_1$ is the first square in the ordering $\prec$, and the second, third and fourth are the other squares in $B_1$, anticlockwise starting from $S_1$;
\item For each $r \in \mathbb{N}$, the initial segments between $B_{r}$ and $B_{r+1}$ are defined by starting with $B_r$, adding the square $S$ with corners $\{(r-1,r),(r,r),(r,r+1),(r-1,r+1)\}$, and then adding the other unit squares in $B_{r+1} \setminus B_{r}$ in anticlockwise order starting from $S$.
\end{itemize}  

Let $S_i$ be the $i$th square in the ordering $\prec$, for each $i \in \mathbb{N}$. Now suppose that we have already defined $\phi$ on $S_1 \cup S_2 \cup \ldots \cup S_n$ in such a way that:
\begin{enumerate}
\item $\phi(v)$ is a vertex of $G$ for all vertices $v \in V(\mathbb{L}^2) \cap (S_1 \cup S_2 \cup \ldots \cup S_n)$;
\item $\phi(e)$ is an edge of $G$ for all edges $e \in E(\mathbb{L}^2) \cap (S_1 \cup S_2 \cup \ldots \cup S_n)$;
\item $\phi(S_i)$ is a closed face of $G$ for all $i \in [n]$;
\item $\phi(e) \neq \phi(e')$ whenever $e$ and $e'$ are distinct, incident edges in $E(\mathbb{L}^2) \cap (S_1 \cup S_2 \cup \ldots \cup S_n)$
\item $\phi|_{S_i}$ is a homeomorphism onto $\phi(S_i)$ for all $i \in [n]$. 
\end{enumerate}
Note that, by our choice of $\prec$, $S_{n+1}$ shares either one or two edges with squares in $\{S_1,\ldots,S_n\}$. Firstly, suppose that $S_{n+1}$ shares exactly one edge with squares in $\{S_1,\ldots,S_n\}$ (say it shares the edge $wx$ with the square $S_i$, and has boundary-cycle $wxyz$). Let $F$ be the unique closed face of $G$ with $\phi(S_i) \cap F = \phi(wx)$; say $F$ has boundary-cycle $\phi(w) \phi(x) a b \phi(w)$. Then extend $\phi$ to $S_{n+1}$ in such a way that
\begin{itemize}
\item $\phi(y) = a$, $\phi(z) = b$, $\phi(xy) = \phi(x) a$, $\phi(yz) = ab$, $\phi(zw) = b\phi(w)$;
\item $\phi(S_{n+1})=F$;
\item $\phi|_{S_{n+1}}$ is a homeomorphism onto $F$.
\end{itemize}
It is easy to see that $\phi$ still satisfies properties 1--5 above. 

Secondly, suppose that $S_{n+1}$ shares two edges with squares in $\{S_1,\ldots,S_n\}$ (say it shares an edge with $S_i$ and an edge with $S_j$). Note that $i \neq j$, and by our choice of the ordering $\prec$, there exists $k \in [n]$ and three corners $q,r,s$ of $S_k$, such that $S_i \cap S_k = qr$, $S_j \cap S_k = rs$ and $S_i \cap S_j = \{r\}$. Say that $S_k$ has boundary-cycle $pqrsp$, $S_i$ has boundary-cycle $qrvwq$, $S_j$ has boundary-cycle $rstur$, and $S_{n+1}$ has boundary-cycle $rvxur$. 

By properties 3 and 4, $\phi(S_k),\phi(S_i)$ and $\phi(S_j)$ are distinct closed faces of $G$; note that they have boundary-cycles
$$\phi(r) \phi(s) \phi(p) \phi(q) \phi(r),\ \phi(r) \phi(q) \phi(w) \phi(v) \phi(r)\ \textrm{and}\ \phi(r) \phi(u) \phi(t) \phi(s) \phi(r)$$
respectively. There is one other closed face of $G$ meeting the vertex $\phi(r)$; call this closed face $F$. The boundary-cycle of $F$ must be of the form $\phi(r) \phi(v) a \phi (u) \phi(r)$ for some $a \in V(G)$. Extend $\phi$ to $S_{n+1}$ in such a way that $\phi(x) = a$, $\phi(vx) = \phi(v) a$, $\phi(ux) = \phi(u) a$, and $\phi(S_{n+1}) = F$ with $\phi|_{S_{n+1}}$ being a homeomorphism onto $F$. It is easy to see that $\phi$ still satisfies properties 1--5 above.

By properties 1,2 and 4, and the fact that both $\mathbb{L}^2$ and $G$ are 4-regular, $\phi|_{V(\mathbb{L}^2)}$ is a covering map (in the graph sense) from the graph $\mathbb{L}^2$ to the graph $G$. Since $G$ is connected, we have $\phi(\mathbb{L}^2)=G$. Therefore, since $G$ is a quadrangulation of $\mathbb{R}^2$, we have $\phi(\mathbb{R}^2)=\mathbb{R}^2$. By properties 1--5, and the fact that $G$ is a quadrangulation, the map $\phi:\mathbb{R}^2 \to \mathbb{R}^2$ is a covering map. Since $\mathbb{R}^2$ is its own universal cover, $\phi$ is a homeomorphism from $\mathbb{R}^2$ to itself. It follows that $\phi|_{V(\mathbb{L}^2)}:V(\mathbb{L}^2) \to V(G)$ is an isomorphism of quadrangulations. Hence, $G$ is isomorphic to $\mathbb{L}^2$ as a quadrangulation of $\mathbb{R}^2$, as required.
\end{proof}

\begin{remark}
Note that this proof yields a slightly stronger statement than Lemma \ref{lemma:uniqueness}, namely that there exists a homeomorphism $\phi$ from $\mathbb{R}^2$ to itself, such that $\phi|_{V(\mathbb{L}^2)}:V(\mathbb{L}^2) \to V(G)$ is an isomorphism of quadrangulations.
\end{remark}

We now give a more elementary proof due to Nakamoto \cite{nakamoto-personal}. We need one more useful notion, due to Altshuler \cite{altshuler}.
\begin{comment}
\begin{fact}
If $G$ is a plane graph and $C$ is a cycle in $G$, then $G \setminus E(G)$ has exactly one bounded component (the {\em inside} of $C$), and exactly one unbounded component (the {\em outside} of $C$).
\end{fact}
\end{comment}

Note that if $G$ is a locally finite plane graph (i.e. a graph embedded in the plane), then for each vertex $v$ of $G$, we may list the edges incident to $v$ in a cyclic order, clockwise (or anticlockwise) around $v$.

\begin{definition}
If $G$ is a 4-regular plane graph, a path or cycle $\gamma$ in $G$ is said to be {\em normal} if, when it is directed (in either of the two possible directions), then for any three consecutive vertices $v_1,v_2,v_3$ of $\gamma$, when the edges of $G$ incident to $v_2$ are listed in clockwise (cyclic) order around $v_2$, the edges $v_1 v_2$ and $v_3 v_2$ are not next to one another in the order. In other words, there is exactly one edge of $G \setminus E(\gamma)$ meeting $v_2$ on either side of the path $v_1 v_2 v_3$:
\end{definition}

\begin{center}
\begin{tikzpicture}
\draw [black] plot [smooth, tension=1] coordinates { (-1,-0.2) (0,0) (1,0.2) (2,0) (3,0.2) (4,0) (5,-0.2)};
\draw [black] plot [smooth, tension=1] coordinates { (2,-2) (2.2,-1) (2,0) (2.2,1) (2,2)};
\draw (0,0) node[minimum size=6pt,inner sep=0pt,circle,fill=black,label=$v_1$] {}
(2,0) node[minimum size=6pt,inner sep=0pt,circle,fill=black,label={above left:$v_2$}] {}
(4,0) node[minimum size=6pt,inner sep=0pt,circle,fill=black,label=$v_3$] {}
(5,0.2) node {$\gamma$}
(2,2) node[minimum size=6pt,inner sep=0pt,circle,fill=black] {}
(2,-2) node[minimum size=6pt,inner sep=0pt,circle, fill=black] {};
\end{tikzpicture}
\end{center}

\begin{proof}[Second proof of Lemma \ref{lemma:uniqueness}]
Let $G$ be a 4-regular quadrangulation of $\mathbb{R}^2$. Choose any edge $\{v,w\}$ of $G$. Let $\gamma$ be the unique edge-maximal path or cycle in $G$ which is normal and contains the edge $\{v,w\}$. Note that $\gamma$ is either a doubly infinite path, or a cycle. We claim that $\gamma$ cannot be a cycle. Indeed, suppose for a contradiction that $\gamma$ is a cycle. Let $\gamma = v_1 v_2 v_3 \ldots v_l v_1$, where $v_1 = v$ and $v_2 = w$, ordering the vertices clockwise. Then for each $i \in [l]$, there is exactly one edge of $G \setminus E(\gamma)$ which meets $v_i$ and lies in the interior of the cycle $\gamma$. Let $w_i$ be the other end-vertex of this edge. We make the following.
\begin{claim}
\label{claim:disjoint}
$w_i \neq v_j$ for all $i,j$.
\end{claim}
\begin{proof}[Proof of claim]
Throughout, addition and subtraction of indices will be modulo $l$. Suppose for a contradiction that $w_i = v_j$ for some $i \neq j \in [l]$. Choose such a pair $i,j$ with the smallest possible cyclic distance $d(i,j)$. By symmetry (interchanging $i$ and $j$ if necessary), we may assume that the clockwise distance from $i$ to $j$ is at most the clockwise distance from $j$ to $i$. Note that $d(i,j) \geq 2$. First, suppose that $d(i,j)=2$. Then $j=i+2$ and $v_i v_{i+1} v_j v_i$ is a triangle forming part of the boundary of a face of $G$, contradicting the fact that $G$ is a quadrangulation. Now suppose instead that $d(i,j) \geq 3$. Then $v_i v_{i+1} \ldots v_{j-1} v_j v_i$ is a cycle in $G$ of length at least 4. Note that the path $w_{i+1} v_{i+1} v_i v_j v_{j-1}$ is a sub-path of a single face-cycle, so $w_{i+1} = v_{j-1}$, i.e. $v_{i+1}$ and $v_{j-1}$ are joined by an edge in the interior of $\gamma$, so $w_{i+1}=v_{j-1}$. But this contradicts the minimality of $d(i,j)$, proving the claim.
\end{proof}

We now make the following.
\begin{claim}
\label{claim:distinct}
$w_i \neq w_j$ for all $i \neq j$.
\end{claim}
\begin{proof}[Proof of claim]
Again, addition and subtraction of indices will be modulo $l$. Suppose for a contradiction that $w_i = w_j$ for some $i \neq j$. Choose such a pair $i,j$ with $d(i,j)$ minimal. By symmetry (interchanging $i$ and $j$ if necessary), we may assume that the clockwise distance from $i$ to $j$ is at most the clockwise distance from $j$ to $i$. First suppose that $d(i,j)=1$; then $j=i+1$. Then the triangle $v_i w_i v_{i+1} v_i$ forms part of the boundary of a face of $G$, contradicting the fact that $G$ is a quadrangulation. Secondly, suppose that $d(i,j)=2$. Then $j=i+2$. By the minimality of $d(i,j)$, we have $w_{i+1} \neq w_i$. Note that the path $w_i v_i v_{i+1} w_{i+1}$ forms part of the boundary of a face of $G$, so we must have $w_i w_{i+1} \in E(G)$ and $w_i v_i v_{i+1} w_{i+1} w_i$ being a face-cycle of $G$. By exactly the same argument, $w_i v_{i+2} v_{i+1} w_{i+1} w_i$ is also a face-cycle of $G$. But then $w_{i+1}$ has degree 2, contradicting the fact that $G$ is 4-regular.

Finally, suppose that $d(i,j) \geq 3$. Note that in this case, $v_{i-1} \neq v_{j+1}$. By the minimality of $d(i,j)$, we have $w_{i+1} \neq w_i$ and $w_{j-1} \neq w_i$. But then $w_i v_i v_{i+1} w_i$ is a sub-path of a face-cycle of $G$, so $w_{i+1}w_i \in E(G)$ and $w_i v_i v_{i+1} w_{i+1} w_i$ is a face-cycle of $G$. Similarly, $w_i v_j v_{j-1} w_{j-1}$ is a sub-path of a face-cycle of $G$, so $w_{j-1}w_i \in E(G)$ and $w_i v_j v_{j-1} w_{j-1} w_i$ is a face-cycle of $G$. It follows that $v_{i-1} v_i w_i v_j v_{j+1}$ is a sub-path of a face-cycle of $G$, contradicting the fact that $G$ is a quadrangulation. 
\end{proof}

We now know that for each $i$, $w_i v_i v_{i+1} w_{i+1}$ is a sub-path of a face-cycle of $G$. Hence, for each $i$, $w_{i} w_{i+1} \in E(G)$ and $w_i v_i v_{i+1} w_{i+1}w_i$ is a face-cycle of $G$. Hence, $\gamma_2 := w_1 w_2 \ldots w_l w_1$ is a cycle in $G$ of length $l$, lying in the interior of the normal cycle $\gamma = v_1 v_2 \ldots v_l$. Note that $\gamma_2$ is also a normal cycle, since for each $i$, exactly one of the edges incident to $w_i$ and not on $\gamma_2$ lie in the exterior of $\gamma_2$. Hence, we have obtained another normal cycle $\gamma_2$ strictly inside the original normal cycle $\gamma$. Repeating this process, we obtain an infinite sequence of normal $l$-cycles $\gamma_1 = \gamma, \gamma_2, \gamma_3, \ldots$ such that $\gamma_{t+1}$ lies strictly in the interior of $\gamma_t$ for all $t \in \mathbb{N}$. Hence, $G$ has a vertex accumulation point, contradicting the fact that it is a quadrangulation.

It follows that $\gamma$ is a doubly infinite path. Let $\gamma = \ldots v_{-2} v_{-1} v_0 v_1 v_2 \ldots$. For each $i \in \mathbb{Z}$, let $w_i$ be the unique neighbour of $v_i$ which is not on $\gamma$ and such that $w_i v_i$ is the next edge after $v_{i-1} v_i$ if the edges incident to $v_i$ are listed in a clockwise direction around $v_i$. Note that for each $i$, $w_i v_i v_{i+1} w_{i+1}$ is a sub-path of a face-cycle of $G$. Hence, for each $i$, $w_{i} w_{i+1} \in E(G)$ and $w_i v_i v_{i+1} w_{i+1}w_i$ is a face-cycle of $G$.

Almost identical arguments to the proofs of Claims \ref{claim:disjoint} and \ref{claim:distinct} show respectively that $w_i \neq v_j$ for all $i,j \in \mathbb{Z}$, and $w_i \neq w_j$ for all $i \neq j$. For completeness, we write out these arguments in full.

First, we claim that $w_i \neq v_j$ for all $i,j$. Indeed, if $w_i = v_j$ for some $i \neq j$, then $v_i$ is joined to $v_j$ for some $i \neq j$. Let $i,j$ be such a pair with $|i-j|$ minimal. By symmetry, we may assume that $i < j$. Clearly, we have $j-i \geq 2$. If $j-i=2$, then the triangle $v_i v_{i+2} v_{i+1} v_i$ forms part of a face-cycle of $G$, contradicting the fact that $G$ is a quadrangulation. Suppose instead that $j-i \geq 3$. Then the path $v_{i+1} v_i v_j v_{j-1}$ forms a sub-path of a face-cycle of $G$, so $v_{i+1} v_{j-1} \in E(G)$, and therefore $w_{i+1}=v_{j-1}$, contradicting the minimality of $|i-j|$.

Next, we claim that $w_i \neq w_j$ for all $i \neq j$. Suppose for a contradiction that $w_i = w_j$ for some $i \neq j$. Choose such a pair $i,j$ with $|i-j|$ minimal. By symmetry (interchanging $i$ and $j$ if necessary), we may assume that $i < j$. If $j-i=1$, then the triangle $v_i w_i v_{i+1} v_i$ forms part of a face-cycle of $G$, contradicting the fact that $G$ is a quadrangulation. If $j-i=2$, then by the minimality of $|i-j|$, we have $w_{i+1} \neq w_i$. But then $w_i v_i v_{i+1} w_i$ is a sub-path of a face-cycle of $G$, so $w_{i+1}w_i \in E(G)$ and $w_i v_i v_{i+1} w_{i+1} w_i$ is a face-cycle of $G$, and similarly, $w_{i} v_{i+2} v_{i+1} w_{i+1} w_i$ is a face-cycle of $G$. Hence, $w_{i+1}$ has degree 2, contradicting the fact that $G$ is 4-regular. Finally, if $|i-j| \geq 3$, then by the minimality of $|i-j|$, we have $w_{i+1} \neq w_i$, $w_{j-1} \neq w_i$, and $w_{i+1} \neq v_{j-1}$. But then $w_i v_i v_{i+1} w_i$ is a sub-path of a face-cycle of $G$, so $w_{i+1}w_i \in E(G)$ and $w_i v_i v_{i+1} w_{i+1} w_i$ is a face-cycle of $G$. Similarly, $w_i v_j v_{j-1} w_{j-1}$ is a sub-path of a face-cycle of $G$, so $w_{j-1}w_i \in E(G)$ and $w_i v_j v_{j-1} w_{j-1} w_i$ is a face-cycle of $G$. It follows that $v_{i-1} v_i w_i v_j v_{j+1}$ is a sub-path of a face-cycle of $G$, contradicting the fact that $G$ is a quadrangulation.

It follows that $\ldots w_{-2} w_{-1} w_0 w_1 w_2 \ldots $ is also a doubly infinite normal path in $G$, vertex-disjoint from $\gamma$, with $v_i w_i \in E(G)$ for all $i \in \mathbb{Z}$. Define $v_i^{0} = v_i$ for all $i \in \mathbb{Z}$ and define $v_{i}^{1} = w_i$ for all $i \in \mathbb{Z}$. By induction, and repeating the same argument `below' $\gamma$ (i.e., replacing `clockwise' by `anticlockwise' in the definition of the $w_i$), we find distinct vertices $(v_i^{j})_{i,j \in \mathbb{Z}}$ such that for each $j \in \mathbb{Z}$,
$$\gamma^{(j)} := \ldots v_{-2}^{j} v_{-1}^{j} v_0^{j} v_{1}^{j} v_{2}^{j} \ldots$$
is a doubly infinite normal path in $G$, and $v_i^{j} v_{i}^{j+1} \in E(G)$ for all $j \in \mathbb{Z}$. Note that $v_i^j v_{i+1}^j \in E(G)$ for all $(i,j) \in \mathbb{Z}^2$, and that $v_i^j v_{i+1}^j v_{i+1}^{j+1} v_{i}^{j+1} v_i^j$ is a face-cycle of $G$ for all $(i,j) \in \mathbb{Z}^2$.

Now define a map $\phi: V(\mathbb{L}^2) \to V(G)$ by $\phi(i,j) = v_i^{j}$. By construction, $\phi$ is an injective graph homomorphism which maps faces of $\mathbb{L}^2$ to faces of $G$. Since $G$ is connected, $\phi$ is surjective. Hence, $\phi$ is a graph isomorphism which preserves faces, so is an isomorphism of quadrangulations.
\end{proof}


\subsection*{Acknowledgements}
We would like to thank \'Eric Colin de Verdi\`ere, Tsachik Gelander, Agelos Georgakopoulos, Atsuhiro Nakamoto, Behrang Noohi, Oliver Riordan and Neil Strickland for very helpful discussions.

\begin{thebibliography}{99}
\bibitem{altshuler} A. Altshuler, Hamiltonian circuits in some maps on the torus, {\em Discrete Mathematics} 1 (1972) 299--314.

\bibitem{in-preparation} I. Benjamini and D. Ellis, On random graphs which are locally indistinguishable from a lattice, in preparation.

\bibitem{coarse-geometry} I. Benjamini, {\em Coarse geometry and randomness.} Lecture notes from the 41st Probability Summer School held in Saint-Flour, 2011. Lecture Notes in Mathematics, 2100 / \'Ecole d'\'Et\'e de Probabilit\'es de Saint-Flour. Springer, 2013.

\bibitem{bieberbach-1911} L. Bieberbach, \"Uber die Bewegungsgruppen der Euklidischen R\"aume I, {\em Mathematische Annalen} 70 (1911), 297--336.

\bibitem{bieberbach-1912} L. Bieberbach, \"Uber die Bewegungsgruppen der Euklidischen R\"aume II, {\em Mathematische Annalen} 72 (1912), 400--412.

\bibitem{config} B. Bollob\'as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Preprint Series, Matematisk Institut, Aarhus Universitet, 1979.

\bibitem{bollobas-connected} B. Bollob\'as, Random graphs, in {\em Combinatorics} (ed. H. N. V. Temperley), London Mathematical Society Lecture Notes Series, 52, Cambridge University Press, Cambridge (1981), 80--102.

\bibitem{bollobas-cycles} B. Bollob\'as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, {\em European Journal of Combinatorics} 1 (1980), 311--316.

\bibitem{bollobas} B. Bollob\'as, The asymptotic number of unlabelled $d$-regular graphs, {\em Journal of the London Mathematical Society} 26 (1982), pp. 201--206.

\bibitem{brown-connelly} M. Brown and R. Connelly, On graphs with a constant link, II, {\em Discrete Mathematics} 11 (1975), 199--232.

\bibitem{hubaut} F. Buekenhout and X. Hubaut, Locally polar spaces and related rank three groups, {\em J. Algebra} 45 (1977), 391--434.

\bibitem{bugata} P. Bugata, M. Hor\v n\'ak and S. Jendrol, On graphs with given neighbourhoods, {\em Casopis pro pestovani matermatiky} 2 (1989), 146--154.

\bibitem{bulitko} V. Bulitko, O grafach s zadanymi okru\v zeniami ver\v sin, Trudy Mat. Inst. im Steklova, 133 (1973), 78--94. (In Russian.)

\bibitem{busset} D. Busset, Graphs which are locally a cube, {\em Discrete Mathematics} 46 (1983), 221--229.

\bibitem{charlap} L. S. Charlap, {\em Bieberbach Groups and Flat Manifolds}, Springer-Verlag, New York, 1986.

\bibitem{chilton} B. L. Chilton, R. Gould and A. D. Polimeni, A note on graphs whose neighbourhoods are $n$-cycles, {\em Geom. Dedicata} 3 (1974), 289--294.

\bibitem{colin-personal} \'E. Colin de Verdi\`ere, personal communication.

\bibitem{lectures-on-orbifolds} M. W. Davis, {\em Lectures on Orbifolds and Reflection Groups}, in: Advanced Lectures in Mathematics, Volume XVI: Transformation Groups and Moduli Spaces of Curves, ed. Lizhen Ji and Shing-Tung Yau, International Press, Somerville, Massachusetts, USA / Higher Education Press, Beijing, China, 2011. Preprint available at \texttt{http://math.osu.edu/files/08-05-MRI-preprint.pdf}.

\bibitem{dST} M. de la Salle and R. Tessera, Characterizing a vertex-transitive graph by a large ball, preprint.\\
Available at \texttt{http://arxiv.org/abs/1508.02247}.

\bibitem{dirac} G. Dirac, Some theorems on abstract graphs, {\em Proc. London Math. Soc.} 2 (1952), 69--81.

\bibitem{doyen} J. Doyen, X. Hubaud and U. Reynnert, Finite graphs with isomorphic neighbourhoods, in {\em Probl\`emes Combinatoires et Th\'eorie des Graphes}, Colloque C.N.R.S. (Orsay), 1976.

\bibitem{gross-tucker} J. L. Gross and T. W. Tucker, {\em Topological Graph Theory}, Wiley, New York, 1987.

\bibitem{hall-1} J. Hall, Locally Petersen graphs, {\em J. Graph Theory} 4 (1980), 173--187.

\bibitem{hall-2} J. Hall, Graphs with constant link and small degree or order, {\em J. Graph Theory} 9 (1985), 479--544.

\bibitem{hall-3} J. Hall, A local characterisation of the Johnson Scheme, {\em Combinatorica} 7 (1) (1987), 77--85.

\bibitem{hall-4} J. Hall and E. E. Shult, Locally cotriangular graphs, {\em Geom. Dedicata} 18 (1985), 113--159.

\bibitem{hatcher} A. Hatcher, {\em Algebraic Topology}, CUP 2002.

\bibitem{hell} P. Hell, Graphs with given neighbourhoods, I, in: {\em Probl\`emes Combinatoires et Th\'eorie des Graphes} (Proc. Coll. Int. C.N.R.S., Orsay, 1976), 219--223.

\bibitem{nedela-survey} J. H. Kwak and R. Nedela, {\em Graphs and their Coverings}, Lecture Notes Series No. 17, Combinatorial and Computational Mathematics Center, POSTECH, Pohang, Korea, 2005.\\
Available at \texttt{http://www.savbb.sk/}$\sim$\texttt{nedela/graphcov.pdf}.

\bibitem{noy} A. M\'arquez, A. de Mier, M. Noy and M. P. Revuelta, Locally grid graphs: classification and Tutte uniqueness, {\em Discrete Mathematics} 266 (2003), 327--352.

\bibitem{wormald-mckay} B. D. McKay, N. Wormald, Automorphisms of random graphs with specified vertices, {\em Combinatorica} 4 (1984), 325--338.

\bibitem{nakamoto-personal} A. Nakamoto, personal communication.

\bibitem{nedela} R. Nedela, Covering projections of graphs preserving links of vertices and edges, {\em Discrete Mathematics} 134 (1994), 111--124.

\bibitem{nedela-2} R. Nedela, Covering spaces of locally homogeneous graphs, {\em Discrete Mathematics} 121 (1993), 177--188. 

\bibitem{perkel} M. Perkel, Trivalent polygonal graphs, {\em Congr. Numer.} 45 (1984), 45--70.

\bibitem{perkel-2} M. Perkel, Trivalent polygonal graphs of girth 6 and 7, {\em Congr. Numer.} 49 (1985), 129--138.

\bibitem{ronan} M. A. Ronan, On the second homotopy group of certain simplicial complexes and some combinatorial applications, {\em Quarterly J. Math. Oxford} 32 (2) (198), 225--233.

\bibitem{sedlacek} J. Sedla\v cek, Local properties of graphs, {\em Casopis pro pestovani matermatiky} 106 (1981), 290--298.

\bibitem{surowski} D. B. Surowski, Vertex-transitive triangulations of compact orientable 2-manifolds, {\em J. Comb. Theory, Series B} 39 (1985), 371--375.

\bibitem{thom} R. Thom, Espaces fibr\'es en sph\`eres et carr\'es de Steenrod, {\em Annales scientifiques de l'\'Ecole Normale Sup\'erieure} 69 (1952), 109--182.

\bibitem{thomassen-torus} C. Thomassen, Tilings of the Torus and Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface, {\em Transactions of the American Mathematical Society} 323 (1991), 605--635.

\bibitem{orbifolds} W. Thurston, {\em Lectures on Orbifolds}, Chapter 13 of {\em The Geometry and Topology of 3-Manifolds}, unpublished manuscript, available at \texttt{http://library.msri.org/books/gt3m/PDF/13.pdf}.

\bibitem{vince} A. Vince, Locally homogeneous graphs from groups, {\em J. Graph Theory} 5 (1981), 111--115.

\bibitem{wormald-thesis}
N. Wormald, Some Problems in the Enumeration of Labelled Graphs, PhD thesis, University of Newcastle, 1978.

\bibitem{wormald-connected}
N. Wormald, The asymptotic connectivity of labelled regular graphs, {\em Journal of Combinatorial Theory, Series B} 31 (1981), 156--167.

\bibitem{zelinka-1} B. Zelinka, Graphs with prescribed neighbourhood graphs, {\em Math. Slovaca} 35 (1985), 195--197.

\bibitem{zelinka-2} B. Zelinka, Neighbourhood realisations of complements of intersection graphs, {\em Math. Slovaca} 39 (1989), 361--363.

\end{thebibliography}

\end{document}
1409.7587.extracted_bib
{altshuler A. Altshuler, Hamiltonian circuits in some maps on the torus, {\em Discrete Mathematics 1 (1972) 299--314.
1409.7587.extracted_bib
{in-preparation I. Benjamini and D. Ellis, On random graphs which are locally indistinguishable from a lattice, in preparation.
1409.7587.extracted_bib
{coarse-geometry I. Benjamini, {\em Coarse geometry and randomness. Lecture notes from the 41st Probability Summer School held in Saint-Flour, 2011. Lecture Notes in Mathematics, 2100 / \'Ecole d'\'Et\'e de Probabilit\'es de Saint-Flour. Springer, 2013.
1409.7587.extracted_bib
{bieberbach-1911 L. Bieberbach, \"Uber die Bewegungsgruppen der Euklidischen R\"aume I, {\em Mathematische Annalen 70 (1911), 297--336.
1409.7587.extracted_bib
{bieberbach-1912 L. Bieberbach, \"Uber die Bewegungsgruppen der Euklidischen R\"aume II, {\em Mathematische Annalen 72 (1912), 400--412.
1409.7587.extracted_bib
{config B. Bollob\'as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Preprint Series, Matematisk Institut, Aarhus Universitet, 1979.
1409.7587.extracted_bib
{bollobas-connected B. Bollob\'as, Random graphs, in {\em Combinatorics (ed. H. N. V. Temperley), London Mathematical Society Lecture Notes Series, 52, Cambridge University Press, Cambridge (1981), 80--102.
1409.7587.extracted_bib
{bollobas-cycles B. Bollob\'as, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, {\em European Journal of Combinatorics 1 (1980), 311--316.
1409.7587.extracted_bib
{bollobas B. Bollob\'as, The asymptotic number of unlabelled $d$-regular graphs, {\em Journal of the London Mathematical Society 26 (1982), pp. 201--206.
1409.7587.extracted_bib
{brown-connelly M. Brown and R. Connelly, On graphs with a constant link, II, {\em Discrete Mathematics 11 (1975), 199--232.
1409.7587.extracted_bib
{hubaut F. Buekenhout and X. Hubaut, Locally polar spaces and related rank three groups, {\em J. Algebra 45 (1977), 391--434.
1409.7587.extracted_bib
{bugata P. Bugata, M. Hor\v n\'ak and S. Jendrol, On graphs with given neighbourhoods, {\em Casopis pro pestovani matermatiky 2 (1989), 146--154.
1409.7587.extracted_bib
{bulitko V. Bulitko, O grafach s zadanymi okru\v zeniami ver\v sin, Trudy Mat. Inst. im Steklova, 133 (1973), 78--94. (In Russian.)
1409.7587.extracted_bib
{busset D. Busset, Graphs which are locally a cube, {\em Discrete Mathematics 46 (1983), 221--229.
1409.7587.extracted_bib
{charlap L. S. Charlap, {\em Bieberbach Groups and Flat Manifolds, Springer-Verlag, New York, 1986.
1409.7587.extracted_bib
{chilton B. L. Chilton, R. Gould and A. D. Polimeni, A note on graphs whose neighbourhoods are $n$-cycles, {\em Geom. Dedicata 3 (1974), 289--294.
1409.7587.extracted_bib
{colin-personal \'E. Colin de Verdi\`ere, personal communication.
1409.7587.extracted_bib
{lectures-on-orbifolds M. W. Davis, {\em Lectures on Orbifolds and Reflection Groups, in: Advanced Lectures in Mathematics, Volume XVI: Transformation Groups and Moduli Spaces of Curves, ed. Lizhen Ji and Shing-Tung Yau, International Press, Somerville, Massachusetts, USA / Higher Education Press, Beijing, China, 2011. Preprint available at http://math.osu.edu/files/08-05-MRI-preprint.pdf.
1409.7587.extracted_bib
{dST M. de la Salle and R. Tessera, Characterizing a vertex-transitive graph by a large ball, preprint.\\ Available at http://arxiv.org/abs/1508.02247.
1409.7587.extracted_bib
{dirac G. Dirac, Some theorems on abstract graphs, {\em Proc. London Math. Soc. 2 (1952), 69--81.
1409.7587.extracted_bib
{doyen J. Doyen, X. Hubaud and U. Reynnert, Finite graphs with isomorphic neighbourhoods, in {\em Probl\`emes Combinatoires et Th\'eorie des Graphes, Colloque C.N.R.S. (Orsay), 1976.
1409.7587.extracted_bib
{gross-tucker J. L. Gross and T. W. Tucker, {\em Topological Graph Theory, Wiley, New York, 1987.
1409.7587.extracted_bib
{hall-1 J. Hall, Locally Petersen graphs, {\em J. Graph Theory 4 (1980), 173--187.
1409.7587.extracted_bib
{hall-2 J. Hall, Graphs with constant link and small degree or order, {\em J. Graph Theory 9 (1985), 479--544.
1409.7587.extracted_bib
{hall-3 J. Hall, A local characterisation of the Johnson Scheme, {\em Combinatorica 7 (1) (1987), 77--85.
1409.7587.extracted_bib
{hall-4 J. Hall and E. E. Shult, Locally cotriangular graphs, {\em Geom. Dedicata 18 (1985), 113--159.
1409.7587.extracted_bib
{hatcher A. Hatcher, {\em Algebraic Topology, CUP 2002.
1409.7587.extracted_bib
{hell P. Hell, Graphs with given neighbourhoods, I, in: {\em Probl\`emes Combinatoires et Th\'eorie des Graphes (Proc. Coll. Int. C.N.R.S., Orsay, 1976), 219--223.
1409.7587.extracted_bib
{nedela-survey J. H. Kwak and R. Nedela, {\em Graphs and their Coverings, Lecture Notes Series No. 17, Combinatorial and Computational Mathematics Center, POSTECH, Pohang, Korea, 2005.\\ Available at http://www.savbb.sk/$\sim$nedela/graphcov.pdf.
1409.7587.extracted_bib
{noy A. M\'arquez, A. de Mier, M. Noy and M. P. Revuelta, Locally grid graphs: classification and Tutte uniqueness, {\em Discrete Mathematics 266 (2003), 327--352.
1409.7587.extracted_bib
{wormald-mckay B. D. McKay, N. Wormald, Automorphisms of random graphs with specified vertices, {\em Combinatorica 4 (1984), 325--338.
1409.7587.extracted_bib
{nakamoto-personal A. Nakamoto, personal communication.
1409.7587.extracted_bib
{nedela R. Nedela, Covering projections of graphs preserving links of vertices and edges, {\em Discrete Mathematics 134 (1994), 111--124.
1409.7587.extracted_bib
{nedela-2 R. Nedela, Covering spaces of locally homogeneous graphs, {\em Discrete Mathematics 121 (1993), 177--188.
1409.7587.extracted_bib
{perkel M. Perkel, Trivalent polygonal graphs, {\em Congr. Numer. 45 (1984), 45--70.
1409.7587.extracted_bib
{perkel-2 M. Perkel, Trivalent polygonal graphs of girth 6 and 7, {\em Congr. Numer. 49 (1985), 129--138.
1409.7587.extracted_bib
{ronan M. A. Ronan, On the second homotopy group of certain simplicial complexes and some combinatorial applications, {\em Quarterly J. Math. Oxford 32 (2) (198), 225--233.
1409.7587.extracted_bib
{sedlacek J. Sedla\v cek, Local properties of graphs, {\em Casopis pro pestovani matermatiky 106 (1981), 290--298.
1409.7587.extracted_bib
{surowski D. B. Surowski, Vertex-transitive triangulations of compact orientable 2-manifolds, {\em J. Comb. Theory, Series B 39 (1985), 371--375.
1409.7587.extracted_bib
{thom R. Thom, Espaces fibr\'es en sph\`eres et carr\'es de Steenrod, {\em Annales scientifiques de l'\'Ecole Normale Sup\'erieure 69 (1952), 109--182.
1409.7587.extracted_bib
{thomassen-torus C. Thomassen, Tilings of the Torus and Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface, {\em Transactions of the American Mathematical Society 323 (1991), 605--635.
1409.7587.extracted_bib
{orbifolds W. Thurston, {\em Lectures on Orbifolds, Chapter 13 of {\em The Geometry and Topology of 3-Manifolds, unpublished manuscript, available at http://library.msri.org/books/gt3m/PDF/13.pdf.
1409.7587.extracted_bib
{vince A. Vince, Locally homogeneous graphs from groups, {\em J. Graph Theory 5 (1981), 111--115.
1409.7587.extracted_bib
{wormald-thesis N. Wormald, Some Problems in the Enumeration of Labelled Graphs, PhD thesis, University of Newcastle, 1978.
1409.7587.extracted_bib
{wormald-connected N. Wormald, The asymptotic connectivity of labelled regular graphs, {\em Journal of Combinatorial Theory, Series B 31 (1981), 156--167.
1409.7587.extracted_bib
{zelinka-1 B. Zelinka, Graphs with prescribed neighbourhood graphs, {\em Math. Slovaca 35 (1985), 195--197.
1409.7587.extracted_bib
{zelinka-2 B. Zelinka, Neighbourhood realisations of complements of intersection graphs, {\em Math. Slovaca 39 (1989), 361--363.