Successive Edge-Disjoint Spanning Trees in Random Graphs

Definitions and mathematical statement

For a finite connected graph with real edge weights, a minimum spanning tree is a spanning tree minimizing the sum of its edge weights. Successive edge-disjoint minimum spanning trees can be obtained by selecting a minimum spanning tree, deleting its edges, and repeating whenever the remaining graph admits a spanning tree. This explains the terminology only: the supplied record does not specify the random graph model, edge-weight distribution, tie-breaking convention, or treatment of a disconnected remaining graph.

The supplied conjectural questions are \[ \rho_k(2k+t)\longrightarrow\rho_\infty(t) \qquad (k\to\infty) \] and, in the notation supplied, \[ \gamma_k\longrightarrow 2k-1. \] Here the record describes $\rho_k$ as a largest-component profile and $\gamma_k$ as a limiting tree weight, but supplies no mathematical definitions of either quantity. In particular, it does not identify the graph whose largest component defines $\rho_k$, the normalization of component sizes or tree weights, the underlying graph-size limit, or the mode of any random convergence. The domain and quantifier for $t$, the admissible arguments of $\rho_k$, and the intended mode of convergence of the profiles are also unspecified. The existence and characterization of $\rho_\infty$ are not given.

The expression $\gamma_k\to 2k-1$ has a target depending on $k$, so its intended meaning requires clarification. For example, the assertions $\gamma_k-(2k-1)\to0$ and $\gamma_k/(2k-1)\to1$ are different possible interpretations; neither is selected here.

Consequently, these displays preserve the supplied questions but do not constitute a fully specified mathematical conjecture. The original extracted text is the incomplete fragment "We conjecture that for Random Graphs: Combinatorics, Complex Networks and Disordered Systems 903". The supplied verification claim concerning the cleaned statement does not resolve the missing definitions or the ambiguous weight asymptotic.

Short English statement

The record asks whether largest-component profiles approach a common shape after shifting time by $2k$, and whether successive limiting tree weights approach the supplied expression $2k-1$. Missing process definitions, convergence conventions, and an ambiguous weight asymptotic prevent a precise complete statement. The supplied open status requires independent review.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30005483$, exact source problem code catalogue entry, title Successive Edge-Disjoint Spanning Trees in Random Graphs, in the Oberwolfach Reports Open Problems collection. Local registry references: data/unsolvedmath/problems.json and catalog/problems.json. No individual proposer is identified; the supplied proposed year is 2023.
• Supplied source citation: Random Graphs: Combinatorics, Complex Networks and Disordered Systems (2023), Oberwolfach Reports, pp. 883--914, DOI 10.4171/owr/2023/16. https://doi.org/10.4171/owr/2023/16. The supplied original fragment includes the apparent page marker 903, but does not provide a complete conjecture.
• Supplied literature source, labeled "OWR 2023 report": https://ems.press/content/serial-article-files/47010?nt=1. The background attributes the collection to Oberwolfach workshop reports and their open-problem discussions.
• Supplied literature assessment dated exactly 2026-08-22: the record labels the problem open because the extracted statement is an incomplete conjectural fragment whose intended claim cannot be established unambiguously. This is supplied dated curation, not an independently verified literature assessment. The background requests independent verification of time-sensitive status and cited claims.
• The record also labels the statement corrected_verified and asserts that it was checked against the official report and preserves its hypotheses, notation, and target. This is a supplied verification claim; no source visit or independent verification is asserted here, and the claim does not reconcile the formulation gaps above.