Tétel: (i) Egy F formulahalmaznak akkor és csak akkor logikai következménye az f formula, ha már F egy F' véges részhalmzának is logikai következménye.
(ii) Egy F formulahalmaz akkor és csak akkor kielégíthető, ha minden véges részhalmaza kielégíthető.
Egy alkalmazás: a sík színezése.
A tér színezési problémája Planet Math.org szerint.
Egy kapcsolódó cikk: Székely László: Erdős on unit distances and the Szemerédi-Trotter theorems
Következmény: (Erdős-deBruijn-tétel) Legyen k egy természets szám. Egy gráf akkor és csak akkor színezhető jól ki k színnel, ha minden véges részgráfja jól kiszínezhető k színnel.