A Note on Graphs Without $k$-Connected Subgraphs

Abstract

Given integers $k\ge 2$ and $n\ge k$, let $e(n,k)$ denote the maximum possible number of edges in an $m$-vertex graph which has no $k$-connected subgraph. It is immediate that $e(n,2)=n–1$. Mader [2] conjectured that for every $k\le 2$, if $n$ is sufficiently large then $c(n,k)\le (1.5k-2)(n–k+1),$ where equality holds whenever $k–1$ divides $n$. In this note we prove that when $n$ is sufficiently large then $e(n,k)\le \frac{193}{120}(k–1)(n–k+1)<1.61(k–1)(n–k+1),$ thereby coming rather close to the conjectured bound.