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?



Do all graphs with $n$ vertices and $m$ edges have a special property?
For $n=53$ and $m=113$, you can't even get close in general. Take 7 copies of $K\_5$ and 3 copies of $K\_6$, all disjoint. Remove any two edges; now you have 53 vertices and 113 edges. No complete bipartite subgraph has more than 6 vertices. If you don't like disconnected graphs, delete 9 more edges without disconnecting any component and add 9 edges to connect the components into a path (the new edges forming bridges). Since bridges can't belong to complete bipartite graphs other than $K\_{1,k}$ you still don't have complete bipartite subgraphs that are big enough.


Regarding practical algorithms for graphs of about this size, first note that if there is a large enough bipartite subgraph then there is one with the smallest side at most 6 vertices. $K\_{6,7}$ is just big enough.
Given $V\_1\subseteq V$, the largest bipartite subgraph with one side equal to $V\_1$ is given by $V\_1$ plus all the common neighbours of $V\_1$. So you can find the answer just by looking at all $\sum\_{k=1}^6\binom{53}{k}=26144847$ subsets of size up to 6. For a computer that's not many.


For super-fast implementation, store the neighbours of each vertex as bit-vectors in 64-bit words. The common neighbours of a set are the bitwise AND of the neighbours of the vertices and almost all modern computers can count the 1-bits in a word in a single machine instruction. Make the subsets recursively (or as 6 nested loops if you don't need it too general) so you can give up on a branch of the search that already has too few or sufficiently many common neighbours. I'm confident that a running time which is a small fraction of a second in the worst case is possible.


