Låt L vara en given familj av så kallade förbjudna grafer. Låta ex (n, L betecknar det maximala antalet kanter en enkel graf av ordning n kan ha utan att innehålla subgrafer från L. En typisk extrem graf problem är att bestämma ex (n, L, eller åtminstone hitta bra gränser på det. Resultat som hävdar att för en given L finns det en mycket mindre L* 9 L för vilka ex (n, L --ex (n, L* kommer att kallas kompaktitet resultat. Huvudsyftet med detta papper är att bevisa vissa kompaktitet resultat för fallet när L består av cykler. Ett av våra viktigaste verktyg kommer att hitta lägre gränser på antalet vägar P1 + I i en graf av n hörn och E kanter., häxa är i själva verket en "övermättad" version av en välkänd teorem av Erdős och Gallai.
I REF antar Erdős och Simonovits följande.
Compactness results in extremal graph theory
{'venue': 'Combinatorica', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}