Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 622

claims/: The 1 claim page of Problem 622, one per claimant's result; the problem's standing derives from them.

Statement. Let $G$ be a regular graph with $2n$ vertices and degree $n+1$ . Must $G$ have $\gg 2^{2n}$ subsets that are spanned by a cycle?

Formulation. A subset is spanned by a cycle when the induced graph on it has a Hamilton cycle, using exactly its vertices. Distinct subsets are counted, not distinct cycles on the same subset.

Status. Proved by Draganić, Keevash, and Müyesser (2025). The site labels the problem PROVED and credits the resolution to [DKM25]; the result is recorded as an accepted claim, on the refereed venue and the site's acceptance, on its claim page, from which the frontmatter standing is derived.

Source. T. F. Bloom, Erdős Problem #622, erdosproblems.com/622, accessed 2026-09-05. The original source key [Er99] is retained from the site.

References.

[Er99] P. Erdős, A selection of problems and results in combinatorics, Combinatorics, Probability and Computing 8 (1999), 1–6, DOI.
[DKM25] N. Draganić, P. Keevash, and A. Müyesser, Cyclic Subsets in Regular Dirac Graphs, International Mathematics Research Notices 2025(14), rnaf215, 1–16, DOI; arXiv:2503.01826v2.

Formalization. None recorded (site and community database, 2026-09-05; no formal-conjectures file).

Current assessment

The site (2026-09-05) labels the problem PROVED, reports the asymptotic result of [DKM25] and records no formalized statement; its discussion holds one comment, about a bibliography link that had been broken, and its proof-claims tab is empty.

A separate 2026-09-05 search checked arXiv version history, the published IMRN article, author publication pages, later papers, and indexed announcements including X. It found related results about lower regular degrees, tournaments, and clique factors, rather than a replacement of the exact result for this question; details and primary links are in the related-literature record and the clique-factor record. No materially different accepted graph proof was identified.

The page for Theorem 1.2 records reconstruction gaps in its finer proof; those are distinct from the public proved status of the original question.

Progress and known results

This is a question of Erdős and Faudree, recorded in Erdős's A selection of problems and results in combinatorics (1999), [Er99]. The degree and regularity assumptions are essential: $K_{n,n}$ disproves the degree- $n$ variant, while adding a spanning star inside each part of $K_{n,n}$ disproves the minimum-degree- $n+1$ variant. The counts and arguments are in the introductory sharpness remarks.

Draganić, Keevash, and Müyesser prove a positive absolute lower bound for the proportion of cyclic subsets in Theorem 2.2, and the sharp asymptotic bound

\operatorname{Cyc}(G)\ge\left(\frac12-o(1)\right)2^{2n}

in Theorem 4.1. Their method splits regular Dirac graphs into bidense graphs, two almost cliques, and almost-bipartite graphs. In the last case, internal linear forests compensate for the imbalance between the two sampled parts.

Their stronger published Theorem 1.2 states that, for sufficiently large $n$ , a minimum is attained by $K_{n-1,n+1}$ with a $2$ -factor added inside its larger part. Every such example has cyclic-subset proportion $1/2+3/(2\sqrt{\pi n})+O(n^{-3/2})$ by Lemma 5.1. Thus the constant $1/2$ works for all sufficiently large orders and no fixed larger constant can work asymptotically. The source leaves the minimizing choice of $2$ -factor unspecified.

The related nonregular sufficient degree condition, published as $N/2+\Omega(\sqrt N)$ , is recorded with its source proof-pointer limits in Proposition 1.3.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (29)

Draganić, Keevash and Müyesser's positive proportion of cyclic subsets problems/extremal_graph_theory/E0622/claims Extremal and Structural Graph Theory extremal_graph_theory/draganic_2025_cyclic_subsets_regular_dirac_graphs Conjecture 6.1: clique factors in random subsets External inputs used in the cyclic-subset proofs Lemma 2.3: random subsets of bidense regular graphs Lemma 2.4: random subsets of two almost cliques Lemma 2.5: random subsets in the almost bipartite case Lemma 3.12: differences of independent half-binomials Lemma 3.4: joining two almost complete parts Lemma 3.5: Hamilton connectivity above Dirac degree Lemma 3.6: a matching across any substantial cut Lemma 3.7: a good almost bipartite cut is Hamiltonian Lemma 3.8: bipartite Hamilton connectivity Lemma 3.9: vertex covers on opposite halves Lemma 4.2: robust good cuts from two internal covers Lemma 4.3: dense subgraphs with bounded maximum degree Lemma 4.4: sampling a minimum vertex cover Lemma 4.6: concentration of sampled edge counts Lemma 4.7: the Gaussian inequality for good cuts Lemma 5.1: the second-order term for the extremal family Lemma 5.2: binomial intervals and moderate tails Proposition 1.3: a square-root excess in minimum degree Further directions after the cyclic-subset theorem Remarks on sharpness of the hypotheses Theorem 1.2: the exact extremal family Theorem 2.2: a positive fraction of subsets are cyclic Theorem 4.1: asymptotically half of all subsets are cyclic

Graph