Paperlane

no. 13 · Wednesday 11 November 2026

Sufficient average degree conditions for the existence of large highly connected subgraphs

Maximilian Krone

math.CO · v2

Abstract

Mader proved that every sufficiently large graph with average degree at least $(2+\sqrt{2})k-1$ has a $(k+1)$-connected subgraph. He also conjectured that already an average degree of at least $3k-1$ is sufficient. The best known sufficient factor was improved by multiple authors but never reached $3$. In the present paper, it is further improved to $3.109$. In addition, the obtained $(k+1)$-connected subgraph is guaranteed to have more than $1.2k$ vertices. Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater $(k+1)$-connected subgraphs. In particular, for $σ\geq \sqrt{\frac{2}{3}}$, every graph with average degree at least $\big(2+σ+\frac{1}{3σ}\big)k-1$ has a $(k+1)$-connected subgraph on more than $(1+σ)k$ vertices, where the factor $2+σ+\frac{1}{3σ}$ is asymptotically sharp for $σ\geq 1$.

comments
New version: Theorem 1(1) has been extended, a generalization of high connectivity and order has been studied, and the structure of all proofs has been revised
fields
Combinatorics
pdf ↗ page arXiv:2511.08256 ↗