 Solution

Always true. An all-different constraint of arity $k$ requires $k$ distinct values. If $|D|<k$, the pigeonhole principle makes even one such constraint impossible. Since $m>0$, at least one is present, and consequently