[proofplan] We prove the equivalence by taking complements. If $C$ covers every edge, then two vertices outside $C$ cannot be adjacent, so $V \setminus C$ is independent. Conversely, if $V \setminus C$ is independent, then no edge can lie entirely outside $C$, so every edge must meet $C$. The cardinality statement follows by applying the equivalence to a set and its complement, using $|V \setminus C| = |V| - |C|$ for finite $V$. [/proofplan] [step:Show that the complement of a vertex cover is independent] Assume that $C$ is a vertex cover of $G$. By definition, for every edge $e \in E$, one has $e \cap C \neq \varnothing$. Let $I := V \setminus C$. To prove that $I$ is independent, let $u,v \in I$ with $u \neq v$. Suppose, for contradiction, that $\{u,v\} \in E$. Since $u \in I$ and $v \in I$, neither $u$ nor $v$ lies in $C$, so \begin{align*} \{u,v\} \cap C = \varnothing. \end{align*} This contradicts the vertex cover property of $C$. Hence no two distinct vertices of $I$ are adjacent, and therefore $I = V \setminus C$ is an independent set. [guided] Assume that $C$ is a vertex cover of $G$. This means that every edge has at least one endpoint in $C$: for each $e \in E$, \begin{align*} e \cap C \neq \varnothing. \end{align*} Define the complement set $I := V \setminus C$. We want to show that $I$ is independent. By definition, this means that there are no distinct vertices $u,v \in I$ such that $\{u,v\}$ is an edge of $G$. Take arbitrary distinct vertices $u,v \in I$. Since $I = V \setminus C$, the statements $u \in I$ and $v \in I$ mean exactly that $u \notin C$ and $v \notin C$. If $\{u,v\}$ were an edge, then that edge would have no endpoint in $C$, so \begin{align*} \{u,v\} \cap C = \varnothing. \end{align*} But this is impossible because $C$ is a vertex cover and every edge must meet $C$. Therefore $\{u,v\} \notin E$. Since the distinct vertices $u,v \in I$ were arbitrary, no edge joins two vertices of $I$, and $I = V \setminus C$ is independent. [/guided] [/step] [step:Show that the complement of an independent set is a vertex cover] Assume that $V \setminus C$ is an independent set. Let $e \in E$ be arbitrary. Since $G$ is undirected and $E$ consists of two-element subsets of $V$, there exist distinct vertices $u,v \in V$ such that $e = \{u,v\}$. Suppose, for contradiction, that $e \cap C = \varnothing$. Then $u \notin C$ and $v \notin C$, so $u,v \in V \setminus C$. Since $e = \{u,v\} \in E$, this contradicts the independence of $V \setminus C$. Therefore $e \cap C \neq \varnothing$. Since $e \in E$ was arbitrary, every edge of $G$ meets $C$, so $C$ is a vertex cover. [/step] [step:Translate the cardinality threshold by taking complements] Assume first that $G$ has a vertex cover $C \subset V$ with $|C| \leq k$. By the equivalence already proved, $I := V \setminus C$ is an independent set. Since $V$ is finite, \begin{align*} |I| = |V \setminus C| = |V| - |C| \geq |V| - k. \end{align*} Thus $G$ has an independent set of cardinality at least $|V|-k$. Conversely, assume that $G$ has an independent set $I \subset V$ with $|I| \geq |V|-k$. Define $C := V \setminus I$. By the equivalence already proved, $C$ is a vertex cover. Again using finiteness of $V$, \begin{align*} |C| = |V \setminus I| = |V| - |I| \leq k. \end{align*} Thus $G$ has a vertex cover of cardinality at most $k$. Combining the two implications proves the threshold equivalence. [/step]