În teoria grafurilor, teorema Erdős–Pose ( Pal Erdős și Lajos Pose ) afirmă că există o funcție f ( k ) astfel încât, pentru orice număr natural k , orice graf fie conține k cicluri separate de vârfuri , fie el are un ciclu de tăiere a mulțimii de f ( k ) vârfuri care intersectează orice ciclu. Mai mult, f ( k ) = O( k log k ) în O notație mare . Având în vedere această teoremă, se spune că ciclurile au proprietatea Erdős–Pose .
Teorema afirmă că pentru orice număr finit k , există o valoare (minimă) f ( k ) pentru care, în orice grafic care nu are k cicluri deconectate de vârfuri, toate ciclurile pot fi acoperite de f ( k ) vârfuri. Acest lucru generalizează un rezultat nepublicat de Bolobash , care afirmă că f (2) = 3 . Erdős și Poza [1] au obținut limite c 1 k log k < f ( k ) < c 2 k log k în cazul general. Acest rezultat sugerează că, deși există infinit de multe grafice fără k cicluri deconectate, ele se încadrează într-un număr finit de clase pur și simplu descrise. Pentru cazul k = 2 , Lovasz [2] a oferit o descriere completă. Voss [3] a demonstrat că f (3) = 6 și 9 ≤ f (4) ≤ 12 .
O familie F de grafice sau hipergrafe , prin definiție, are proprietatea Erdős–Pose dacă există o funcție f : N → N astfel încât pentru orice (hiper-)graf G și orice număr întreg k una dintre următoarele este adevărată:
Definiția este adesea formulată după cum urmează. Dacă notăm cu ν ( G ) numărul maxim de vârfuri ale subgrafelor disjunse ale lui G care sunt izomorfe cu graficele din F și cu τ ( G ) numărul maxim de vârfuri a căror eliminare din G lasă graficul fără grafice izomorfe cu graficele din F , atunci ν ( G ) ≤ f ( τ ( G )) , pentru o funcție f : N → N independentă de G .