Local Recognition of Graphs and Geometries

Definitions and mathematical statement

In the usual simple undirected graph convention, let $\Delta$ be a fixed graph. For a graph $\Gamma$ and vertex $v$, write \[ N_\Gamma(v)=\{w\in V(\Gamma):vw\in E(\Gamma)\} \] for its open neighborhood, and $\Gamma[N_\Gamma(v)]$ for the subgraph induced by those neighbors. The graph $\Gamma$ is locally $\Delta$ if \[ \Gamma[N_\Gamma(v)]\cong\Delta\quad\text{for every }v\in V(\Gamma). \] The local-recognition problem is to classify, up to graph isomorphism, all $\Gamma$ satisfying this condition for the given $\Delta$.

No vertex-transitivity or connectedness assumption is in the supplied target. If disconnected graphs are allowed, each connected component must itself be locally $\Delta$, so a connected classification gives the unrestricted nonempty cases by disjoint unions. If $\Delta$ is finite with $k$ vertices, locally $\Delta$ graphs are $k$-regular, but they need not be finite. The extract does not specify whether finite graphs, infinite graphs, or a special family of local graphs is intended; these restrictions must be stated when selecting a particular classification problem.

The literature assessment checked on 21 August 2026 explicitly identifies this as a broad programme rather than one theorem. It selects no specific $\Delta$ and provides no complete classification. Thus the registry's open label does not mean that local recognition is unresolved for every individual local graph; the question and its answer depend on $\Delta$ and the ambient graph class. No additional geometry axiom is inserted merely because the original passage discusses synthetic geometry.

Short English statement

For a prescribed graph $\Delta$, classify graphs whose induced neighbor graph at every vertex is $\Delta$. The source gives the general local-recognition programme, without choosing a specific local graph or finite/connected ambient class.

Sources

• Groups and Geometries (2005), Oberwolfach Reports, DOI 10.4171/owr/2005/12, pp. 647--721, https://doi.org/10.4171/owr/2005/12.
• Literature assessment checked 21 August 2026: "original local-recognition context," https://doi.org/10.4171/owr/2005/12; "local-recognition research," https://doi.org/10.1007/s10801-009-0201-4.
• Local UnsolvedMath registry, permanent ID $30000204$, exact source code catalogue entry, created 25 August 2026 and updated 16 September 2026. The clean statement is labelled corrected and verified; the assessment records a programme-level classification request.