Bollobás--Eldridge--Catlin conjecture for bounded-degree spanning subgraphs

Let Δ\Delta be a positive integer. Let GG and HH be nn-vertex graphs, and write δ(G)\delta(G) for the minimum degree of GG and Δ(H)\Delta(H) for the maximum degree of HH.

Bollobás--Eldridge--Catlin conjecture. If

δ(G)ΔΔ+1n\delta(G)\geq \frac{\Delta}{\Delta+1}n

and Δ(H)Δ\Delta(H)\leq \Delta, then HH is a spanning subgraph of GG.

The conjecture remains open; the source notes that a proof for sufficiently large nn was announced by Kun in 2009, but no manuscript had appeared.

Sources & referencesView supporting material

Primary source

Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa and Mihir Neve, “Robustness of the Sauer-Spencer Theorem”, arXiv:2507.03676 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.