Let $\psi(n)\approx\sqrt{n}$ denote the positive solution to $x^2+2x=n$. Note that if $|V_1||V_2|+|V_1|+|V_2|>n$, then either $|V_1|\geq \psi(n)$ or $|V_2|\geq \psi(n)$. This implies that all subgraphs which satisfy constraint $1$ have a vertex of degree at least $\psi(n)$.
Let $\phi(n)$ denote the largest even integer less than $\psi(n)$. If $m\leq n\phi(n)$, then there exists a graph $G\in\mathcal{G}$ that does not have this property. In particular, any $\phi(n)$-regular graph on $n$ vertices will not have this property. Thus, $m\geq \Omega(n^{1.5})$ is a necessary but not sufficient condition for this property. (As an additional note, you should be able to get a far superior lower bound via an application of the probabilistic method.)
For the specific case of $n=53$ and $m=113$, we can do better than the trivial brute force algorithm. Note that for $$|V_1||V_2|+|V_1|+|V_2|> 53$$
to be satisfied, either $|V_1|\geq 7$ or $|V_2|\geq 7$.
Fix $a\in [7,52]$, let $b$ be the smallest integer such that $ab+a+b>53$. Note $b\leq 6$. Find the set $U$ of all vertices with degree at least $a$. For each subset $S\in\binom{U}{b}$, check whether the common neighborhood of $S$ has at least $a$ vertices. The key idea is that because $G$ is sparse, $U$ cannot be too large. There are likely many tricks you could use to increase the speed of your implementation. For example, any vertex whose degree is less than $b$ cannot be part of the desired subgraph, so you could prune all low-degree vertices from your graph first. This is equivalent to saying that the desired subgraph (if it exists) must be contained in the $b$-core of your graph.