V teorii grafů Erdős–Poseův teorém ( Pal Erdős a Lajos Pose ) říká, že existuje funkce f ( k ) taková, že pro libovolné přirozené číslo k každý graf buď obsahuje k cyklů oddělených vrcholy , nebo má cyklus ořezávání množiny f ( k ) vrcholů , které protínají libovolný cyklus. Navíc f ( k ) = O( k log k ) v notaci O Big . S ohledem na tento teorém se říká, že cykly mají vlastnost Erdős–Pose .
Věta říká, že pro libovolné konečné číslo k existuje nějaká (minimální) hodnota f ( k ) , pro kterou v libovolném grafu, který nemá k cyklů odpojených od vrcholu, mohou být všechny cykly pokryty f ( k ) vrcholy. To zobecňuje nepublikovaný výsledek Bolobashe , který uvádí, že f (2) = 3 . Erdős a Poza [1] získali meze c 1 k log k < f ( k ) < c 2 k log k v obecném případě. Tento výsledek naznačuje, že ačkoli existuje nekonečně mnoho grafů bez k nespojených cyklů, spadají do konečného počtu jednoduše popsatelných tříd. Pro případ k = 2 podal Lovasz [2] úplný popis. Voss [3] dokázal, že f (3) = 6 a 9 ≤ f (4) ≤ 12 .
Rodina F grafů nebo hypergrafů má podle definice vlastnost Erdős–Pose, pokud existuje funkce f : N → N taková, že pro jakýkoli (hyper-)graf G a jakékoli celé číslo k platí jedna z následujících:
Definice je často formulována následovně. Označíme-li ν ( G ) maximální počet vrcholů disjunktních podgrafů G , které jsou izomorfní s grafy z F a τ ( G ) maximální počet vrcholů, jejichž odstraněním z G zůstane graf bez grafů izomorfní ke grafům z F , pak ν ( G ) ≤ f ( τ ( G )) , pro nějakou funkci f : N → N nezávisle na G .