I don't know how to type subscripts here, so K(m,n) denotes the complete bipartite graph on parts of cardinality m and n.

My question is; How many nonisomorphic spanning subgraphs are there of of K(m,n)? This is such an obvious question, it has probably been answered. I just don't know whereto look. There is an obvious, but complex to use, recursion for the constructions. Given the set of nonisomorphic subgraphs of K(m-1,n) -- or of Km,n-1) -- appending the n-1 edges from the missing vertex in the first case or m-1 in the second edges in all inequivalent ways will generate the set for K(m,n). But this is not a numerical problem so no simple recursion seems possible -- yet it may have well been solved using Polya's counting theorem. Do any of you know the answer, or where it can be found?

treesof $K(m,n)$, then you may find more information at www.austinmohr.com/work (under "Master's Thesis"). Moreover, the algorithm used to enumerate the trees should be easy to adapt to counting any sort of subgraph, though the runtime will suffer. There is a polytime algorithm for determining isomorphism between trees, but there is not yet one for general graphs. – Austin Mohr Feb 15 '13 at 2:11