The graph \(H_{x,y}\)  with partition \(V_{A}^{\prime }, V_{B}^{\prime }\)  is a family of lower bound graphs wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{H}\) . Therefore, thm: general lb framework gives an \(\tilde{\Omega }(k^2)\)  lower bound for the problem of deciding whether a graph with \(O(k \log k)\)  vertices has a vertex cover of weight \(W = 4(k - 1) + 4 \log _{2} k\)  as shown in [1]}. Therefore for a graph with \(n\) -vertices we get an \(\tilde{\Omega }(n^{2})\)  lower bound which completes the proof of thm:MWVC-lower-bound-main-theorem.
