Liu and Ning's interpolation conjecture for 2-connected subgraphs

From papers

For a fixed integer q3q\ge 3, let n0(q)n_0(q) be an integer threshold. Let GG be a 2-connected graph of order nn0(q)n\ge n_0(q), and write δ(G)\delta(G) for its minimum degree. Liu and Ning's conjecture. Every such graph satisfying

δ(G)nq\delta(G)\ge \frac{n}{q}

contains a 22-connected subgraph of order \ell for every {4,5,,n}\ell\in\{4,5,\ldots,n\}. This conjecture seeks an asymptotic minimum-degree threshold guaranteeing 2-connected subgraphs of every possible order; the preceding results establish stronger degree thresholds, namely approximately n/3n/3 and n/4n/4, but the proposed n/qn/q threshold for every fixed q3q\ge 3 remains unresolved.

Progress summary

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

Sources & referencesView supporting material

Primary source

Heng Yang, “k-Connected Subgraphs of All Orders in Large Graphs with Minimum Degree at Least n/q”, arXiv:2607.18964 (2026).

Solutions 0

No solutions have been posted yet.