Number of subgraphs with a given number of nodes Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$.
The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where
$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$
Let $k_1 \leq |E_G|$ and $k_2 \leq |V_G|$ be given in input.
I would like to determine the number $k_3$ of edge-induced subgraphs of $G$ having $k_1$ edges and $k_2$ nodes. Clearly, I don't want to enumerate all the (exponentially many) subgraphs of $G$ having $k_1$ edges.

Questions:

Is it possible to determine $k_3$ in time polynomial in $|E_G|$?
What if $G$ is 3-regular?
What if $G$ is 3-regular planar?
What if $G$ is 3-regular planar bipartite?
Which is the best known algorithm to compute $k_3$? $\longleftarrow$ Added on 30/08/2012
Let $f(G, k_1, k_2)$ be the counting problem that you have defined. Then
$$g(G) = \sum_{k_1 = 0}^{|V_G| / 2} f(G, k_1, 2 k_1)$$
counts the number of matchings in $G$, which only uses a linear number of oracle calls to your problem.

Since counting matchings in 3-regular planar graphs is #P-hard (see ref below), your questions (1), (2), and (3) all give a #P-hard problem. Your last question (4) probably gives a #P-hard problem as well because counting matchings in 3-regular biparitie planar graphs is probably #P-hard, but I don't know if anyone has proved this.  The closest that I know of is that


counting matchings in 2,3-regular biparitie planar graphs is #P-hard and
counting matchings in biparitie planar graphs of max degree 6 is #P-hard.


The reference that I promised above is Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP by Jin-Yi Cai, Pinyan Lu, Mingji Xia. Theorem 6.1 proves that counting matchings in 3-regular planar graphs is #P-hard in the special case that $[y_0, y_1, y_2] = [1,0,1]$ and $[x_0, x_1, x_2, x_3] = [1,1,0,0]$.