Graph invariant that encodes number of subgraphs with $i$ vertices and $j$ edges Suppose we have invariant of graph $G$ that tells us number of subgraphs with $i$ vertices and $j$ edges for every setting of $i$ and $j$. Is there a name for it?
I searched for "subgraph polynomial", but that comes up as something else.

Have you ever hear about the Tutte Polynomial $T(G;x,y)$ ? it is defined for any graph $G$ (and even defined for matroids) and it has many evaluations which count combinatorial structures related to $G$. Also, many other polynomials related to $G$ are just the Tutte polynomial under some clever substitution (like the chromatic polynomial and the flow polynomial) A good starting point to learn about $T(G;x,y)$ is 
http://en.wikipedia.org/wiki/Tutte_polynomial
It contains many good references on the subject. A last word: Computing the Tutte polynomial is #P-complete in almost any point of the complex plane.
