I grafteori siger Erdős-Pose-sætningen ( Pal Erdős og Lajos Pose ), at der eksisterer en funktion f ( k ), således at enhver graf for ethvert naturligt tal k enten indeholder k toppunkt-adskilte cyklusser , eller den har en cyklus , der skærer det sæt af f ( k ) hjørner, der skærer enhver cyklus. Desuden f ( k ) = O( k log k ) i O Big notation . I lyset af denne teorem siges cykler at have Erdős-Pose-egenskaben .
Sætningen siger, at for ethvert endeligt tal k er der en eller anden (minimums)værdi f ( k ) , for hvilken alle cyklusser kan dækkes af f ( k ) hjørner i enhver graf, der ikke har k toppunktafbrudte cyklusser . Dette generaliserer et upubliceret resultat af Bolobash , som siger, at f (2) = 3 . Erdős og Poza [1] opnåede grænser c 1 k log k < f ( k ) < c 2 k log k i det generelle tilfælde. Dette resultat antyder, at selvom der er uendeligt mange grafer uden k afbrudte cyklusser, falder de ind i et begrænset antal enkelt beskrivelige klasser. For tilfældet k = 2 gav Lovasz [2] en fuldstændig beskrivelse. Voss [3] beviste, at f (3) = 6 og 9 ≤ f (4) ≤ 12 .
En familie F af grafer eller hypergrafer har per definition egenskaben Erdős–Pose, hvis der findes en funktion f : N → N , således at for enhver (hyper-)graf G og ethvert heltal k er et af følgende sandt:
Definitionen er ofte formuleret som følger. Hvis vi angiver med ν ( G ) det maksimale antal hjørner af usammenhængende undergrafer af G , der er isomorfe til grafer fra F og med τ ( G ), det maksimale antal knudepunkter, hvis fjernelse fra G efterlader grafen uden grafer, som er isomorfe til grafer fra F , derefter ν ( G ) ≤ f ( τ ( G ) ) , for nogle funktioner f : N → N uafhængig af G .