Regular Graph Families with Connected Higher-Order Links

Definitions and mathematical statement

The supplied record asks for infinite families of graphs with prescribed regularity parameters and connected links of vertices, edges, triangles, copies of $K_4$, and copies of $K_5$. Here $K_r$ denotes the complete graph on $r$ vertices. The record does not define $(a,b,c,d,e)$-regularity, so a complete mathematical formulation cannot be recovered from the supplied text alone.

For clarity, under the convention that graphs are undirected and simple, the graph link of a nonempty clique $S\subseteq V(G)$ is the induced graph \[ L_G(S)=G\!\left[\bigcap_{v\in S}N_G(v)\right], \qquad N_G(v)=\{w\in V(G):\{v,w\}\in E(G)\}. \] Thus the link consists of the common neighbors of the vertices of $S$, together with all edges of $G$ between those neighbors. This is an explicit conventional interpretation of the source's word "neighborhood"; its agreement with the intended source definition requires review. A nonempty graph is connected if every two of its vertices can be joined by a finite path. Whether an empty link is permitted, and whether it is regarded as connected, must be specified separately.

Let $\mathscr G$ stand for the intended class of graphs, and let $\mathsf{Reg}_{a,b,c,d,e}(G)$ stand for the source's undefined assertion that $G$ is $(a,b,c,d,e)$-regular. These are placeholders for missing specifications, not additional hypotheses established by the record. With these qualifications, the universally quantified supplied statement has the following schema: \[ \begin{aligned} &\forall (a,b,c,d,e)\in{\mathbb{Z}}_{>0}^{5}\quad \exists\,\mathcal F\subseteq\mathscr G\text{ infinite}\quad \forall G\in\mathcal F,\\ &\qquad \mathsf{Reg}_{a,b,c,d,e}(G) \quad\text{and}\quad \forall r\in\{1,2,3,4,5\}\ \forall S\subseteq V(G),\\ &\qquad\qquad \left(|S|=r\ \text{and}\ G[S]\cong K_r\right) \Longrightarrow L_G(S)\text{ is connected}. \end{aligned} \] The five listed clique sizes correspond respectively to vertices, edges, triangles, copies of $K_4$, and copies of $K_5$. The link condition is universally quantified over cliques that actually occur; the supplied record does not separately require all five clique sizes to occur.

This is an unresolved statement schema. In particular, the regularity predicate, the graph domain, the meaning of an infinite family, and the treatment of empty links require clarification before it becomes a fully specified existence problem. The source's original wording does not explicitly quantify the parameters, whereas its supplied clean statement says "for arbitrary positive integers"; the displayed schema preserves that latter quantifier without claiming it has been independently checked.

Short English statement

For every positive integer tuple $(a,b,c,d,e)$, the supplied statement asks whether infinitely many graphs with that regularity pattern can have connected common-neighbor links at every vertex, edge, triangle, $K_4$, and $K_5$. The regularity pattern and several graph conventions are missing, so the intended precise existence question requires human review. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004124$, title "Regular Graph Families with Connected Higher-Order Links," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2019.
• Supplied source citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, pp. 1113--1189, DOI 10.4171/owr/2019/19. Supplied source URL: https://doi.org/10.4171/owr/2019/19. The background describes these reports as records of mathematical workshops and their open-problem discussions.
• Supplied literature source: "Oberwolfach Report 19/2019, connected-link regular graphs," https://doi.org/10.4171/owr/2019/19. The literature assessment dated 2026-08-22 labels the problem open and reports that its check located no primary result resolving the stated existence question. This is supplied dated curation, not an independently verified literature assessment. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official report was checked directly, with the clean statement preserving the target while restoring definitions and removing source-dependent wording. This is a supplied verification claim, not verification performed for this draft; the supplied record still does not include a definition of $(a,b,c,d,e)$-regularity.