How can we prove that the following theorem is valid for almost perfect secrecy?

Question

We have the following theorem:

Let $\Pi$ be a perfectly-secret scheme over message space $M$, and let $K$ be determined by $Gen$. Then $|K| ≥ |M|$.

How can we prove that the above theorem is valid for almost perfect secrecy? The definition for almost perfect secrecy is as follows:

The encryption scheme $\Pi = (Gen,Enc,Dec)$ over a message space $M$ is almost perfectly secret or $\varepsilon$-perfectly secret if for every probability distribution over $M$, $\forall m \in M$ and $\forall c \in C$ for which $Pr[C = c] > 0$ and for a constant $\varepsilon < 1$:

$$|Pr[M = m|C = c] - Pr[M = m]| < \varepsilon$$

EDIT

Answer 1

Encrypt an arbitrary message to get a ciphertext $c$, then use all keys to decrypt $c$. If $|K| \lt |M|$, there exists a message $m$ which can not be decrypted from $c$ using any key.

Then $|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$ and since we can assign an arbitrary distribution to our message space, we can make $\Pr[M=m] > \epsilon$. This violates your definition of $\epsilon$-perfect secrecy, thus we must have $|K| \geq |M|$.

Note that there is a different definition of an $\epsilon$-perfect secrecy, the one requiring that an adversary playing a game could not succeed with a probability higher than $\frac{1}{2} + \epsilon$. Such definition allows to have fewer keys than messages. For more information, have a look at Almost (epsilon) perfect secrecy - lower bound of keyspace size