Minimum vertex cover refutes the exact-hardness approximation claim

Minimum vertex cover has NP-hard exact optimization: by [F2] its threshold problem is NP-complete, so a polynomial-time exact optimizer would decide an NP-complete problem and imply $P=NP$. Yet [F3] gives a deterministic polynomial-time algorithm that always returns a vertex cover of size at most $2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Thus the existence of a constant-factor approximation is compatible with exact NP-hardness and refutes the unqualified claim of [F1]; it does not establish or refute a lower bound conditioned on $P\mathrm{\ne }NP$.

The four-vertex path $P_4$ with vertices $v_1,v_2,v_3,v_4$ and edges $v_1{v}_2,v_2{v}_3,v_3{v}_4$ exhibits the two matchings. The single edge $v_2{v}_3$ is a maximal matching whose endpoint set $\{v_2,v_3\}$ is a vertex cover: it meets $v_1{v}_2$ at $v_2$, $v_2{v}_3$ itself, and $v_3{v}_4$ at $v_3$. One vertex meets at most two of the three edges, so no cover of size one exists and ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}(P_4)=2$; the matching lower bound is $\mathrm{\mid }M\mathrm{\mid }=1\le 2$. Scanning edges in the order $v_1{v}_2,v_2{v}_3,v_3{v}_4$ instead inserts the disjoint outer edges $v_1{v}_2$ and $v_3{v}_4$, a maximal matching whose endpoint set is all of $V$ with $\mathrm{\mid }C\mathrm{\mid }=4=2\cdot {\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}(P_4)$, realizing the factor-two upper bound on this graph.

Minimum vertex cover has NP-hard exact optimization and a polynomial-time factor-two approximation by step 1.1, so it refutes the unqualified claim of [F1]. The path in step 2.1 illustrates the tightness of the factor but does not establish the uniform ratio; that is the content of the general theorem in [F3]. A conditional claim that approximation is impossible unless $P=NP$ is not refuted here.