On the number of edges in a graph with no (k+1)-connected subgraphs

Anton Bernshteyn, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review


Mader proved that for k≥1 and n≥2k, every n-vertex graph with no (k+1)-connected subgraphs has at most (Formula presented.) edges. He also conjectured that for n large with respect to k, every such graph has at most (Formula presented.) edges. Yuster improved Mader's upper bound to (Formula presented.). In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to (Formula presented.) for (Formula presented.).

Original languageEnglish (US)
Pages (from-to)682-688
Number of pages7
JournalDiscrete Mathematics
Issue number2
StatePublished - Feb 6 2016


  • Average degree
  • Connectivity
  • k-connected subgraphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the number of edges in a graph with no (k+1)-connected subgraphs'. Together they form a unique fingerprint.

Cite this