Complete minors and average degree: A short proof

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review


We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree (Formula presented.) has a complete minor of order (Formula presented.).

Original languageEnglish (US)
JournalJournal of Graph Theory
StateAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • clique minors
  • probabilistic methods

Cite this