Edge-Disjoint Hamilton Cycles in Random Graphs

Definitions and mathematical statement

For each integer $n\geq 3$, let $[n]=\{1,\ldots,n\}$. For $p\in[0,1]$, the binomial random graph $G(n,p)$ is the simple undirected graph on $[n]$ in which each unordered pair of distinct vertices is an edge independently with probability $p$. For a graph $G$, write $\delta(G)=\min_{v\in V(G)}\deg_G(v)$. A Hamilton cycle is a cycle containing every vertex of $G$ exactly once. Hamilton cycles are edge-disjoint if no edge belongs to two of them. Let $h(G)$ be the maximum number of pairwise edge-disjoint Hamilton cycles in $G$, allowing the empty collection, so that $h(G)=0$ when no Hamilton cycle exists. Since each Hamilton cycle uses two edges at every vertex, $h(G)\leq\lfloor\delta(G)/2\rfloor$.

The question in the supplied corrected statement is: for every deterministic sequence $(p_n)_{n\geq3}$ with $p_n\in[0,1]$, is it true that, for $G_n\sim G(n,p_n)$, \[ \lim_{n\to\infty}\Pr\!\left(h(G_n)=\left\lfloor\frac{\delta(G_n)}{2}\right\rfloor\right)=1? \] Here "with high probability" means that the displayed probability tends to one as $n\to\infty$. When $\delta(G_n)\leq1$, the requested collection has size zero and is permitted to be empty.

There are unresolved qualifications in the supplied record. Its original formulation asks about the random graph process when the requested number $r=r(n)$ of edge-disjoint Hamilton cycles grows with $n$, and asks for a threshold in terms of minimum degree and edge probability. It specifies neither a growth range for $r$ nor a precise threshold assertion. That formulation is not automatically equivalent to the displayed binomial-model question. The supplied verification field says that the official report was checked and that an explicit question later in the same contribution replaced the vague extraction; the displayed question follows that supplied correction. However, the supplied dated literature assessment still describes a contextual extraction recording a partial tight-Hamilton-cycle-packing result and says that the intended residual question is unidentified. No precise partial-result statement is supplied, so none is asserted here. The record's open-status label and verification label are supplied curation, not independently verified conclusions of this draft.

Short English statement

For every sequence of edge probabilities, does a binomial random graph, with probability tending to one, contain as many edge-disjoint Hamilton cycles as its minimum degree permits? This follows the supplied corrected statement. The original growing-$r$ process question and the older contextual assessment leave unresolved source and formulation differences.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30001652$, title "Edge-Disjoint Hamilton Cycles in Random Graphs," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record assigns the year 2011 and supplies no named proposer.
• Supplied report citation: Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01, https://doi.org/10.4171/owr/2011/01. The supplied literature-source entry labels this same reference "Oberwolfach Report 01/2011." The background describes these reports as documenting mathematical workshops and their open-problem discussions. No precise page or contribution identifying this question is supplied.
• Supplied statement-verification metadata labels the statement corrected_verified and reports that the official report was checked and a vague extraction was replaced by an explicit problem later in the same contribution. This is a report of supplied verification, not a claim that the source was visited for this draft. The record's update timestamp is 2026-09-16T12:06:53Z.
• Supplied literature assessment checked on 2026-08-21: status "open"; the extraction is described as contextual rather than a complete problem, recording a partial tight-Hamilton-cycle-packing result while leaving the intended residual question unidentified. The listed source is https://doi.org/10.4171/owr/2011/01. This assessment is supplied dated curation derived from the supplied OWR curation, not independently verified; its time-sensitive status and cited claims require independent verification.