With the goal of finding how good is the complexity we obtain for a \((1+\varepsilon )\) -approximation of MVC in sssec:UBunweightedVC, we tried to prove a lower bound for it, with respect to \(n\)  (We mention that the \(1/\varepsilon \)  term in the complexity is unavoidable, due to a straightforward adaptation of the lower bound given in [1]}. The quadratic lower bounds in this paper, as well as in previous papers [2]}, [3]}, are all obtained by lower bound graphs of small cuts (logarithmic size). We show that any construction which has a cut of size \(o(n)\)  cannot give any super-constant lower bound for a \((1+\varepsilon )\) -approximation of MVC, for any \(\varepsilon = O(1)\) .
