[Proof of thm:MWVC-lower-bound-main-theorem]
Censor-Hillel et al. [1]} show that the MVC lower bound graph \(G_{x,y}\)  is a family of lower bound graphs for the \(\mathsf {CONGEST}\)  model wrt the set-disjointness function \(f=DISJ_{k^{2}}\)  and the predicate \(P_{G}\)  which asks whether the graph \(G\)  has a vertex cover of size \(W = 4(k - 1) + 4\log k\) . The vertices of \(G_{x,y}\)  are partitioned into \(V_{A} = A_{1} \cup A_{2} \cup \lbrace f_{S}^{i}, t_{S}^{i} \mid 1 \le i \le \log _{2} k, S \in \lbrace A_{1}, A_{2}\rbrace \rbrace \)  and \(V_{B} = V(G_{x,y}) \setminus V_{B}\) , with the cut size being \(|E(V_{A}, V_{B})| = O(\log k)\) .
