2-factors in dense graphs

Noga Alon, Eldar Fischer

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2/3 n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven here for all sufficiently large n.

Original languageEnglish (US)
Pages (from-to)13-23
Number of pages11
JournalDiscrete Mathematics
Issue number1-3
StatePublished - May 20 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of '2-factors in dense graphs'. Together they form a unique fingerprint.

Cite this