Definitions
Let $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$).
Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$.
Let $\le$ be a total order on $V$.
For each $v \in V$, let $V_v \subseteq V$ consist of the nodes that are within distance $r$ from $v$ in $G$ (the shortest path from $v$ to any $u \in V_v$ has at most $r$ edges), and let $G_v$ be the subgraph of $G$ induced by $V_v$. Recall that we assumed that $G$ has a high girth; hence $G_v$ is a tree. Let $\le_v$ be the restriction of $\le$ to $V_v$.
We say that an edge $\{u,v\} \in E$ is good if $(G_u,\le_u)$ and $(G_v,\le_v)$ are isomorphic. That is, there is a bijection $f\colon V_u \to V_v$ that preserves adjacencies ( $\{x,y\} \in E$ iff $\{f(x),f(y)\} \in E$ ) and order ($x \le y$ iff $f(x) \le f(y)$). Otherwise an edge is bad.
We say that $(G,\le)$ is $\epsilon$-good if there are at least $(1-\epsilon)|E|$ good edges.
Question
Let $d = 4$. Does there exist an $\epsilon$-good pair $(G,\le)$ for any $\epsilon > 0$ and any $r$ and $g$ (with $r \ll g$)?
Remarks:
I would like to know the answer for a general $d$, but $d = 4$ is the first non-trivial case.
The size of $G$ does not matter, as long as it is finite. I do not need a construction of $G$; mere existence or non-existence is sufficient.
Examples
If $d = 2$, the answer is "yes". We can simply take a sufficiently long cycle, and order the nodes along the cycle. There are some bad edges near the edge that joins the largest and the smallest node, but all other edges are good: for almost all nodes $v$, the pair $(G_v,\le_v)$ is just a path with $2r+1$ nodes in an increasing order.
If $r = 0$, the answer is "yes". Just take a regular high-girth graph.
If $g$ is sufficiently small, the answer is "yes" for any even $d$. Just take a $(d/2)$-dimensional grid graph (with the boundaries wrapped around to make it $d$-regular), and order the nodes lexicographically by their coordinates. Again we have some bad edges near the boundaries of the grid, but we can make the number of bad edges arbitrarily small.
If $G$ does not need to be finite, the answer is "yes" for any even $d$. A regular infinite tree has a total order such that all edges are good.
If $d$ is odd and $r$ is sufficiently large, the answer is "no". In essence, Naor & Stockmeyer (1995) show that every node is incident to at least one non-good edge.
Background
(This section can be safely skipped.)
The question is related to the foundations of distributed computing, and in particular to local algorithms.
What we would like to understand is the following: in which situations the existence of a total order helps with local symmetry breaking in a distributed system. Intuitively, each node $v$ of $G$ has to produce an output that is a function of $(G_v,\le_v)$, i.e., a function of the local neighbourhood of $v$. If an edge $e = \{u,v\}$ is bad, there is some local symmetry-breaking information available near $e$, and nodes $u$ and $v$ may produce different outputs; if the edge is good, then nodes $u$ and $v$ are locally indistinguishable and they have to produce the same output.
For many classical graph problems it is known that a total order does not help (much weaker relations provide essentially the same amount of symmetry-breaking information), but some cases are still open – and a general result that covers the case of all high-girth graphs could be a breakthrough.
This might be a win-win question: regardless of the answer, we learn something new. If the answer is "yes", we might be able to derive new, stronger lower-bound results; if the answer is "no", we might be able to design faster algorithms that exploit the local symmetry-breaking information that is available in any $(G,\le)$.
Of course in the real world we do not have a total order on $V$; we have something more: each node $v \in V$ has a unique label $\ell(v) \in \mathbb{N}$. But bridging the gap between a total order and unique labels is usually more straightforward; often a Ramsey-like argument shows that (in the worst case) the labels do not provide any information that is not available in a total order.
