A Note on Graphs Without \(k\)-Connected Subgraphs

Abstract

Given integers \(k \geq 2\) and \(n \geq 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 \leq 2\), if \(n\) is sufficiently large then \(c(n, k) \leq (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) \leq \frac{193}{120}(k – 1)(n – k + 1) < 1.61(k – 1)(n – k + 1),\) thereby coming rather close to the conjectured bound.