[proofplan] We first show that $\mathrm{VERTEX}\text{-}\mathrm{COVER}$ lies in NP by describing a polynomial-time verifier for a proposed vertex cover. For NP-hardness, we give a polynomial-time many-one reduction from $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$, using the complement relation between independent sets and vertex covers in the same graph. The reduction handles the harmless case $k>|V|$ separately by mapping it to a fixed no-instance, and otherwise sends $(G,k)$ to the graph obtained from $G$ by adding one disjoint edge with target size $|V|-k+1$. [/proofplan] [step:Verify vertex covers in polynomial time] Let $(G,k)$ be an instance of $\mathrm{VERTEX}\text{-}\mathrm{COVER}$, where $G=(V,E)$ is a finite simple undirected graph. A certificate is a subset $C \subseteq V$. The verifier checks first that $|C| \leq k$, and then checks, for every edge $e=\{u,v\} \in E$, whether $u \in C$ or $v \in C$. The size check takes time polynomial in $|V|$. The edge check examines each edge once and performs membership tests in $C$, so it takes time polynomial in $|V|+|E|$ after representing $C$ by a Boolean lookup table indexed by the vertices. Therefore $\mathrm{VERTEX}\text{-}\mathrm{COVER} \in \mathrm{NP}$. [/step] [step:Define the many-one reduction from independent set] We reduce from the decision problem $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$, as defined by Independent Set Is NP-Complete: an instance is a pair $(G,k)$, where $G=(V,E)$ is a finite simple undirected graph and $k \in \mathbb{N}$, and the instance is accepted if and only if there exists a subset $S \subseteq V$ such that no edge of $E$ has both endpoints in $S$ and $|S| \geq k$. We use Independent Set Is NP-Complete as the NP-complete source problem. Let $n := |V|$. Define $K_3 := (V_3,E_3)$ to be the triangle graph with vertex set $V_3 := \{r_1,r_2,r_3\}$ and edge set $E_3 := \{\{r_1,r_2\},\{r_2,r_3\},\{r_1,r_3\}\}$. For the case $k \leq n$, choose two fresh vertices $a$ and $b$ with $a,b \notin V$ and $a \neq b$, and define the augmented graph $G_+ := (V_+,E_+)$ by $V_+ := V \cup \{a,b\}$ and $E_+ := E \cup \{\{a,b\}\}$. Define the many-one reduction map $f$ from the set of pairs $(G,k)$, where $G=(V,E)$ is a finite simple undirected graph and $k \in \mathbb{N}$, to the set of pairs $(H,\ell)$, where $H$ is a finite simple undirected graph and $\ell \in \mathbb{N}$. If $k>n$, set $f(G,k) := (K_3,1)$. If $k\leq n$, set $f(G,k) := (G_+,n-k+1)$. The value $n=|V|$ is computable in time polynomial in the encoding length of $G$, the comparison $k>n$ is polynomial-time, and in the second case the construction adds exactly two vertices and one edge. Hence $f$ is computable in polynomial time. [/step] [step:Prove that complements of independent sets are vertex covers] Let $G=(V,E)$ be a finite simple undirected graph, and let $S \subseteq V$. Define $C := V \setminus S$. We claim that $S$ is an independent set in $G$ if and only if $C$ is a vertex cover of $G$. Suppose first that $S$ is independent. Let $e=\{u,v\} \in E$ be arbitrary. Since $S$ is independent, it is not the case that both $u \in S$ and $v \in S$. Therefore at least one of $u$ and $v$ lies in $V \setminus S=C$. Since this holds for every edge $e \in E$, the set $C$ is a vertex cover. Conversely, suppose that $C=V \setminus S$ is a vertex cover. Let $e=\{u,v\} \in E$ be arbitrary. Since $C$ is a vertex cover, at least one of $u$ and $v$ lies in $C$. Hence at least one of $u$ and $v$ does not lie in $S$. Thus no edge of $G$ has both endpoints in $S$, so $S$ is independent. [guided] The reason the complement appears in the reduction is that the two conditions are exact negations at the level of each edge. An independent set forbids an edge from having both endpoints inside $S$. A vertex cover requires each edge to have at least one endpoint inside the chosen covering set. Let $G=(V,E)$ be a finite simple undirected graph, and let $S \subseteq V$ be any subset. Define its complement in the vertex set by setting $C := V \setminus S$. We prove both directions. First assume that $S$ is independent. This means that for every edge $e=\{u,v\} \in E$, the two endpoints are not both contained in $S$. Fix an arbitrary edge $e=\{u,v\} \in E$. Since $S$ is independent, the statement $u \in S$ and $v \in S$ is false. Therefore at least one of $u \notin S$ or $v \notin S$ holds. Because $u,v \in V$, this is the same as saying that at least one of $u \in V \setminus S$ or $v \in V \setminus S$ holds. By the definition $C=V \setminus S$, at least one endpoint of $e$ lies in $C$. Since the edge $e$ was arbitrary, every edge of $G$ has an endpoint in $C$, so $C$ is a vertex cover. Conversely, assume that $C=V \setminus S$ is a vertex cover. Fix an arbitrary edge $e=\{u,v\} \in E$. Since $C$ is a vertex cover, at least one endpoint of $e$ lies in $C$. Thus at least one of $u \notin S$ or $v \notin S$ holds. Consequently the edge $e$ cannot have both endpoints in $S$. Since this holds for every edge $e \in E$, no edge joins two vertices of $S$, and therefore $S$ is an independent set. [/guided] [/step] [step:Translate the size bound under complementation] Let $S \subseteq V$ and define $C := V \setminus S$. Since $S$ and $C$ are disjoint and their union is $V$, finite additivity of cardinality gives \begin{align*} |C| = |V|-|S| = n-|S|. \end{align*} Therefore $|S| \geq k$ if and only if $|C| \leq n-k$. [/step] [step:Conclude the many-one equivalence and NP-completeness] For every instance $(G,k)$ of $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$, with $G=(V,E)$ and $n=|V|$, first suppose $k>n$. No subset of the finite set $V$ has cardinality at least $k$, so $(G,k)$ is a no-instance of $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$. By definition of $f$, we have $f(G,k)=(K_3,1)$. The graph $K_3$ has three edges, and no single vertex is incident to all three of them; hence no subset of $V_3$ of cardinality at most $1$ is a vertex cover. Therefore $(K_3,1)$ is a no-instance of $\mathrm{VERTEX}\text{-}\mathrm{COVER}$. Now suppose $k\leq n$, and let $G_+=(V_+,E_+)$ be the augmented graph defined in the reduction step, where $V_+=V\cup\{a,b\}$ and $E_+=E\cup\{\{a,b\}\}$. If $G$ has an independent set $S \subseteq V$ with $|S|\geq k$, then $V\setminus S$ is a vertex cover of $G$ by the complement lemma. Define $C_+ := (V\setminus S)\cup\{a\}$. The set $C_+$ covers every edge in $E$ because $V\setminus S$ covers every edge of $G$, and it covers the added edge $\{a,b\}$ because $a\in C_+$. Thus $C_+$ is a vertex cover of $G_+$. Its size satisfies \begin{align*} |C_+| = |V|-|S|+1 \leq n-k+1. \end{align*} Conversely, suppose $G_+$ has a vertex cover $C_+\subseteq V_+$ with $|C_+|\leq n-k+1$. Define $C := C_+\cap V$. Every edge in $E$ is also an edge in $E_+$ and has both endpoints in $V$, so the fact that $C_+$ covers every edge of $G_+$ implies that $C$ covers every edge in $E$. Therefore $C$ is a vertex cover of $G$. Since every vertex cover of $G_+$ must contain at least one of $a$ or $b$ to cover the edge $\{a,b\}$, and since neither $a$ nor $b$ lies in $V$, we have \begin{align*} |C| \leq |C_+|-1 \leq n-k. \end{align*} By the complement lemma and the cardinality computation, $S:=V\setminus C$ is an independent set in $G$ with $|S|\geq k$. Thus $(G,k) \in \mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ if and only if $f(G,k) \in \mathrm{VERTEX}\text{-}\mathrm{COVER}$. The map $f$ is computable in polynomial time, so $\mathrm{INDEPENDENT}\text{-}\mathrm{SET} \leq_p \mathrm{VERTEX}\text{-}\mathrm{COVER}$ by the definition of polynomial-time many-one reduction. Since $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ is NP-complete by Independent Set Is NP-Complete, this proves that $\mathrm{VERTEX}\text{-}\mathrm{COVER}$ is NP-hard. Together with $\mathrm{VERTEX}\text{-}\mathrm{COVER} \in \mathrm{NP}$, we conclude that $\mathrm{VERTEX}\text{-}\mathrm{COVER}$ is NP-complete. [/step]