考虑构造某一类二分图：左部的第 $i$ 个点向右部的前 $a_i$ 个点连边，且 $a_i\ge a_{i+1}$。

容易算出，一种方案中满足条件的点集个数为 $$ \sum_{i=1}^n\sum_{j=a_i}^n{n-i\choose j}=k $$ 即 $$ \sum_{i=1}^n\sum_{j=0}^{a_i-1}{n-i\choose j}=2^n-k-1 $$ 容易证明，依次为每个 $a_i$ 选择一个最大的值一定有解。时间复杂度 $O(n^2)$。