Answers are grounded in this paper and cite their sources.
Theoretical proof shows average degree conditions for connected and edge-connected subgraphs.
Mader conjectured that an average degree of at least $3k-1$ is sufficient for the existence of a $(k+1)$-connected subgraph. The following minimum degree version holds: Every graph with minimum degree at least $3k-1$ has a $(k+1)$-connected subgraph on more than $2k$ vertices. Moreover, for triangle-free graphs, already an average degree of at least $2k$ is sufficient for a $(k+1)$-connected subgraph (which has at least $2(k+1)$ vertices). For edge-connectedness (in simple graphs), we prove the following: Every graph of average degree at least $2k$ has a $(k+1)$-edge-connected subgraph on more than $2k$ vertices. Moreover, for every small $α>0$ and for k large enough in terms of $α$, already a minimum degree of at least k+k1/2+α = (1+o(1))k is sufficient for a $(k+1)$-edge-connected subgraph. It is shown that all of these results are sharp in some sense. The results can be used for the decomposition of graphs into two highly (edge-)connected parts.
No takes yet. Share an insight, caveat, or question.
Maximilian Krone (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: