VC ≤p 3H-VC

Suppose $\langle H,k\rangle\in\mathrm{3H\text{-}VC}$; then some $\hat U\subseteq\hat V$ covers $H$ with $|\hat U|\le k$.

Here the naive proof collapses. $\hat U$ cannot be taken as it stands: it lives in $\hat V$, and $\hat V$ holds vertices outside $V$; if $\hat U$ contains any, it is not a subset of $V$ and asking "does it cover $G$" has no meaning at all. Note the asymmetry against the forward direction: there we received a set inside $V$, and a set inside $V$ is automatically a set inside $\hat V$; here the direction reverses and it breaks.

Build $U\subseteq V$: for each $v\in\hat U$ — if $v\in V$, put $v$ into $U$; otherwise, by construction some edge $xy\in E$ has $v=v_{xy}$, and we put $x$ into $U$.

(This construction is not part of the reduction — it is part of the proof, so its running time needs no analysis.)

Immediately: $U\subseteq V$ by construction, and $|U|\le|\hat U|\le k$. Only $\le$, not $=$, since the map $\hat U\to U$ need not be injective: if $v_{xy},v_{xw}\in\hat U$ both translate to $x$. We received $\hat U$ "from the sky" and may not assume it minimal — but $\le k$ suffices, since a cover can always be padded upward.

$U$ covers $G$: let $e\in E$; there are $x,y\in V$ with $e=\{x,y\}$, and by construction $\{x,y,v_{xy}\}\in\hat E$. Since $\hat U$ covers $H$, $\{x,y,v_{xy}\}\cap\hat U\ne\emptyset$. Split into two complementary cases:

Case 1: $x\in\hat U$ or $y\in\hat U$. Then one of them lies in $V$ and in $\hat U$, so the first rule put it into $U$; hence $e\cap U\ne\emptyset$.

Case 2: $x\notin\hat U$ and $y\notin\hat U$. As the intersection is non-empty, necessarily $v_{xy}\in\hat U$; and since $v_{xy}\notin V$, the second rule put $x$ into $U$. Hence again $e\cap U\ne\emptyset$.

Either way $e\cap U\ne\emptyset$, so $U$ covers $G$ with size $\le k$, i.e. $\langle G,k\rangle\in\mathrm{VC}$.