Conditions for embedding between non-oriented graphs

Question

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ and $\operatorname{card} (E_1) < \operatorname{card} (E_2)$, is the graph $G_1$ isomorphic with a subgraph of $G_2$? The proof must be based on a non-deterministic algorithm.

Answer 1

Pick, non-deterministicly, an injection $f:V_1 \to V_2$ (in other words, pick, once and for all, a numbering of the vertices of $G_1$, and pick, non-deterministically, an ordered list of $|V_1|$ elements from $V_2$). Check whether this is an isomorphism onto its image subgraph. If not, pick another injection. Rinse and repeat.

The isomorphism check is naively linear in $|E_1|\cdot |E_2| < |V_1|^2 \cdot |V_2|^2$: For every pair $(e_1, e_2)$ with $e_1 \in E_1, e_2 \in E_2$, see whether the end points of $e_1$ are sent to the endpoints of $e_2$ by $f$. There are $|E_1| \cdot |E_2|$ such pairs. The check is therefore polynomial time, and thus the whole algorithm is $NP$.