gpt 6 astra ultra attempt on Math-1066

Nearly spanning regular subgraphs

Definitions and mathematical statement

A finite simple graph $G$ is $r$-regular if every vertex has exactly $r$ neighbours. A $k$-regular subgraph $H$ consists of a vertex set $U\subseteq V(G)$ and an edge set $F\subseteq E(G[U])$ such that every vertex of $(U,F)$ has degree exactly $k$. Edges inside $U$ may be omitted, so $H$ need not be induced. It also need not be connected.

The conjecture states that for every integer $k\geq1$ and every real $\varepsilon$ with $0<\varepsilon<1$, there is an integer $r_0=r_0(k,\varepsilon)\geq k$ such that, for every integer $r\geq r_0$ and every nonempty finite simple $r$-regular graph $G$, one can find a $k$-regular subgraph $H$ satisfying \[ |V(H)|\geq(1-\varepsilon)|V(G)|. \] Restricting to $\varepsilon<1$ gives the substantive part of the source's all-positive-$\varepsilon$ formulation; larger errors follow from any smaller positive error.

The threshold may depend on the desired degree and the fraction of vertices one is prepared to discard, but not on the order, connectedness, or other features of $G$. The conclusion demands exact regularity on the retained vertices, not merely average degree $k$ or degrees close to $k$. For odd $k$, the handshaking identity forces $|V(H)|$ to be even; the permitted vertex deletion allows this necessary parity condition to be met.

Short English statement

Does every sufficiently high-degree regular simple graph contain an exactly prescribed-degree regular subgraph covering almost all vertices?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Current literature and precise scope.

The original question is attributed to Alon and Mubayi in [S2]. A preprint by Sivashankar submitted on 17 September 2026 [R1] announces an affirmative answer for all $k,r$ with uncovered proportion $O_k(r^{-1/2})$. Its abstract was checked on 1 October 2026. This attempt does not independently certify that new proof, and the canonical historical "open" label above should not be read as a current claim that no solution has been announced. The work below independently proves two exact spanning subcases and a necessary obstruction to demanding zero error in general. It is not a new proof of the full announced result.

Every regular bipartite graph has the required spanning factor.

Let $G$ be an $r$-regular bipartite graph with classes $X,Y$ and $r\ge1$. Counting edges gives $|X|=|Y|$. For every $U\subseteq X$, all $r|U|$ edges incident with $U$ end in $N(U)$, and at most $r|N(U)|$ edges can do so. Hence $|N(U)|\ge|U|$. Hall's condition therefore holds, and a perfect matching exists.

For completeness, Hall's implication can be seen from a maximum matching. If a vertex $x\in X$ were unmatched, follow alternating paths starting at $x$. No reachable vertex of $Y$ can be unmatched, or the matching could be augmented. If $U$ is the set of reachable vertices in $X$, all neighbours of $U$ are reachable in $Y$, and the matching pairs those neighbours to distinct vertices of $U\setminus\{x\}$. This contradicts $|N(U)|\ge|U|$.

Deleting a perfect matching leaves an $(r-1)$-regular bipartite graph on the same classes. Iterating decomposes all edges into $r$ perfect matchings. The union of any $k$ of them, for $1\le k\le r$, is a spanning $k$-regular subgraph. This proves the desired conclusion with no lost vertices for every bipartite instance, including disconnected ones.

Every even regular graph has spanning factors of each even degree.

Let $r=2s$ and suppose $k=2t\le r$. Each connected component of $G$ has an Euler tour: repeatedly traverse unused edges, and splice further closed trails at vertices with unused incident edges. Even degrees prevent a maximal trail from getting stuck away from its start. Orient edges along the resulting tour. Each vertex then has indegree and outdegree exactly $s$.

Form a bipartite graph with a left and a right copy of each original vertex, replacing a directed edge $u\to v$ by $u_Lv_R$. This is an $s$-regular bipartite graph, so the preceding argument decomposes it into $s$ perfect matchings. In the original directed graph each matching selects precisely one outgoing and one incoming edge at every vertex. A finite directed graph with that property is a disjoint union of directed cycles: follow successors, and uniqueness of predecessors prevents a path from entering a cycle from outside.

The original graph is simple and loopless. Consequently these cycles have length at least three; a directed two-cycle would require both orientations of the same original edge. Forgetting orientations gives a spanning $2$-factor. The $s$ factors are edge-disjoint, and the union of any $t$ is a spanning $2t$-regular subgraph. Thus the entire even-$k$, even-$r$ subcase is proved directly, again with zero error.

A parity barrier showing why vertex loss belongs in the question.

For even $r$, the complete graph $K_{r+1}$ has odd order. A spanning $k$-regular subgraph with odd $k$ would have odd total degree $k(r+1)$, contradicting the handshaking identity. More generally, let $G$ be a disjoint union of copies of $K_{r+1}$. Every odd-$k$-regular subgraph uses an even number of vertices from each component. At least one vertex per component is lost, giving uncovered proportion at least $1/(r+1)$. If $k>r$, no such subgraph exists at all, explaining the threshold's necessary lower bound $r_0\ge k$.

The parity obstruction tends to zero as $r$ grows, so it does not contradict the target. It does show why replacing "nearly spanning" by "spanning" would make the unrestricted assertion false. The factor construction above cannot cure odd-degree demands by deleting a few arbitrary vertices: such deletions usually destroy regularity of all remaining degrees, precisely the invariant on which the matching argument relies.

Verification and final status.

Each selected subgraph has exactly the requested degree, rather than merely minimum or average degree, because its component factors are edge-disjoint and spanning. The directed construction explicitly rules out loops and two-cycles before passing to undirected $2$-factors. UNRESOLVED as an independent full proof. The first missing step in this attempt is a general way to retain almost all vertices while correcting the parity and degree defects outside the two proved subcases. The recent announcement [R1] addresses that full question; its proof has not been reproduced or certified here.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3152 (OPG-801), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Nearly spanning regular subgraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/nearly_spanning_regular_subgraphs.

• R1 Varun Sivashankar, Nearly Spanning Regular Subgraphs, arXiv preprint submitted 17 September 2026. Primary abstract checked 1 October 2026; announces the full result with error $O_k(r^{-1/2})$. The independent attempt does not certify the announced proof. https://arxiv.org/abs/2609.19777.