Erdős, som var en av 1900-talets mest produktiva matematiker, arbetade inom de flesta av den diskreta matematikens områden. Särskilt kan nämnas hans bidrag till det elementära beviset av primtalssatsen samt den probabilistiska metoden inom kombinatoriken.