Winning strategy for a given game on graphs
The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$.



Here is a bit of explanation.

Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only output the winning player.

So let us start with the part missing from your answer. Assume a given instance corresponds to a graph that admits a perfect matching. According to your strategy, Player 2 wins in this case which is right. Now assume the same instance is given with one more villain, or ten more villains or one thousand of them. Clearly, player two still wins since adding villains, regardless to how we assign them, only helps the second player. So your claim does not always hold. However, your answer is very close to my claim and have the same intuition. It is only missing a bit of formality.

Claim. Assuming both players are playing optimally, Player 1 wins if and only if, given an instance $I$, the corresponding graph does not admit a matching saturating the set $H$.

So what does that mean? A matching saturates a set of vertices $S$, if each vertex in $S$ is incident to a vertex in the matching.
Now we prove the claim. We show two winning strategies one for Player two when the graph admits a matching the saturates the set $H$ and one for Player two when the graph does not admit such a matching.

Proof. Now assume the graph admits such a matching. Let this matching be $M$. The strategy goes as follows. As long as Player one did not lose, for each choice $h \in H$ for Player one, choose $v \in V$ the vertex matched to $h$ in $M$.

The correctness follows directly from the fact that each vertex of Player two is unique and adjacent to the choice of Player one (due the properties of a matching). Intuitively, Player one will run out of moves at some point (possibly after choosing all heroes in the set $H$).

Now assuming the graph does not admit a matching saturating $H$, according to Hall's theorem, there is a subset $A \subseteq H$, such that $|N(A)| &lt; A$. Choose such a set that is minimal inclusion-wise. We claim that there is a matching $M'$ that saturates $N(A)$. Assuming otherwise, again due to Hall, there is a subset $S \subseteq N(A)$ such that $|N(S)| &lt; S$, but then removing $N(S) \cap A$ from $A$ and $S$ from $N(A)$ yields a subset of $A$ that also contradicts Hall's condition which forms a contradiction to the choice of $A$ to be minimal. Hence, there is a matching $M'$ that saturates $N(A)$.

Now the strategy goes as follow. Choose a vertex in $A$ that is not incident to any edge in $M$. Such a vertex exists since $|N(A)| &lt; |A|$. Choose this vertex at first and for each choice $v \in V$ of player two, choose the vertex $h \in H$ matched to $v$ in $M'$.

Again, it is easy to see that Player two will run out of moves at some point (possibly after choosing all vertices in $N(A)$) and hence, Player one wins.