Erdos es De Brujin egy klasszikus tetele szerint ha egy adott szinre nincs megfelelo szinezes, akkor van egy olyan veges reszhalmaza a siknak, hogy mar az sem szinezheto jol.

Ez szvsz minden grafra igaz: ha 133 szinnel nem szinezheto, akkor valamely veges resze sem szinezheto annyi szinnel (ha kivalasztasibolbol igaz annyi, ami Godel kompaktsaghoz kell)