2025/08/11 by Maximilian Krone, Krone, Maximilian · 1 citation
#math.CO
paper · pdf · doi:10.48550/arxiv.2508.07997
Mader conjectured in 1979 that an average degree of at least 3k-1 in a graph is sufficient for the existence of a (k+1)-connected subgraph. The following minimum degree analogue holds: Every graph with minimum degree at least 3k-1 contains 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-connectivity (in simple graphs), we prove the following: Every graph with average degree at least 2k contains 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+k(1)/(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 are applied to decompose graphs into two highly connected or edge-connected parts.