I have a problem with the final part of the proof. I reduced Vertex Cover to FVS .
An instance of the vertex cover problem consists of an undirected graph G = (V,E), and a number k. The decision problem is to determine if there exists a vertex cover of size at most k in G. Define a new graph H on the vertex set $U_v \cup U_e$, where vertices of $U_v$ = V correspond to the vertices of G, and vertices of $U_e$ = E correspond to edges of G. For every edge e = $(v_1, v_2)$ $\in$ E, there are three edges in H: an edge between vertices v1 and v2 in $U_v$, an edge between v1 $\in$ $U_v$ and e $\in$ $U_e$, and an edge between v2 $\in$ $U_v$ and e $\in$ $U_e$.
Now, i don't now how to prove that H has an FVS of size <= k iff G has a vertex cover of size <= k.
Best Answer
This is a nice reduction. Here is a constructive proof of its correctness, using the notations you gave. Let us also denote the vertex in $U_v$ corresponding to some vertex $v \in V(G)$ as $u_v$ and let us denote the vertex corresponding to some edge $e = (v, w) \in E(G)$ as $u_{v, w}$.
$(\Rightarrow)$ Let $F \subset U_v \cup U_e$ be a feedback vertex set of $H$ of size $k$. Construct the set $F'$ by replacing every vertex $u_{v, w} \in F$ by $u_v$ (and if $u_v$ is already in $F$, then just remove $u_{v, w}$). Now $F'$ is a set of the form $\{u_{v_1}, u_{v_2}, \cdots, u_{v_m}\}$, where $m \leq k$. We now claim that $C = \{v_1, v_2, \cdots, v_m\}$ is a vertex cover of $G$.
The reason for this is because any feedback vertex set $F$ of $H$ must include one of $\{u_v, u_w, u_{v, w}\}$ for every $u_{v, w} \in U_e$, because there is a cycle on these three vertices. When we constructed $F'$ from $F$, we did not violate this property: if we ever removed some vertex $u_{v, w}$ from $F$, we replaced it with $u_v$. This property is enough to guarantee that in $F'$, there is always a vertex $u \in F$ adjacent to every $u_{v, w} \in U_e$. However, in our construction of $H$, the only vertices adjacent to $u_{v, w}$ corresponded to the endpoints of the edge $(v, w)$ in $G$, so indeed every edge in $G$ is incident upon some vertex in $C$. $\square$
To prove the other direction, we'll need the following definition. Let $G = (V, E)$. An induced subgraph $G' \subseteq G$ on $V' \subseteq V$ is the graph $(V', E')$, where $$E' = \{e = (v, w) ~ | ~v \in V', w \in V', (v, w) \in E\}$$ In other words, it's the subgraph of $G$ that is obtained by keeping only the vertices of $G$ in $V'$ and only the edges of $G$ that connect two members of $V'$.
$(\Leftarrow)$ Let $C = \{v_1, v_2, \cdots, v_k\} \subseteq V(G)$ be a vertex cover in $G$. We claim that $F = \{u_{v_1}, u_{v_2}, \cdots, u_{v_k}\}$ is a feedback vertex set of $H$.
By construction, the induced subgraph of $H$ on $F$ is isomorphic to $G$. Since the removal of a vertex cover of $G$ leaves no edges in $G$, removing $F$ from $H$ removes all edges in $H$ connecting $u_v$ and $u_w$, where $v, w \in G$. Hence, any cycle that remains in $H$ cannot contain any such edges. That is, its only edges have one endpoint in $U_e$ and one endpoint in $U_v$. As every cycle has at least one edge, this means that any cycle in the induced subgraph of $H$ on $(U_e \cup U_v) \setminus F$ has some vertex $u_{v, w} \in U_e$.
However, in our construction the only edges in $H$ incident to $u_{v, w} \in U_e$ were from $u_v$ and $u_w$. As $C$ was a vertex cover, for every edge $(v, w) \in E(G)$ one of $v$ or $w$ was in $C$, and hence one of $u_v$ or $u_w$ was necessarily in $F$. Therefore, no such cycle can exist, as any vertex $u_{v, w}$ still in $H$ after the removal of $F$ has at most one edge incident to it. $\square$
When trying to prove the correctness of the reduction, always go back to the intuition that guided you to the reduction you produced. In this case, the intuition (or at least mine) was that the small $3$-cycles $\{u_v, u_w, u_{v, w}\}$ in $H$ of corresponded the edges $(v, w) \in E(G)$. Here, breaking a cycle in $H$ via removal of a vertex would more or less be equivalent to covering an edge in $G$ with that vertex.