Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.

For which values of $n$ and $m$ does the following requirement hold:

$\forall G \in \mathcal{G}$ there exist $V\_1 \subset V,V\_2 \subset V$ such that:

1. $(v\_1 \in V\_1 \land v\_2 \in V\_2) \implies \{v\_1,v\_2\} \in E$,
2. $|V\_1||V\_2|+|V\_1|+|V\_2| \gt n$?

Constraint $1$ is equivalent to say that $V\_1$ and $V\_2$ are the parts of an embedded complete bi-partite subgraph.

I am particularly interested in the case $n=53$ and $m=113$.

Since the above problem might be too difficult, a simpler one could be: how to design an algorithm (with a feasible time for $n=53$ and $m=113$) to decide whether a given graph $G \in \mathcal{G}$ satisfies or not the requirement?

Any hint?