$K_{7,9}$ means the bipartite graph in which one partition has 7 nodes and the other 9 nodes, and all nodes share an edge except those in the same partition.
How many subgraphs of $K_{7,9}$ have 16 nodes and 16 edges?
This was a question in my exercise sheet, and they claim the answer is ${63}\choose{16}$. However I computed that $K_{7,9}$ has $63$ edges and therefore ${63}\choose{16}$ can be interpreted as the number of ways to choose $16$ edges from the graph. But there are clearly subgraphs with $16$ edges that have less than $16$ nodes, therefore the answer must be strictly less than $K_{7,9}$.
Am I correct that the answer cannot be $K_{7,9}$? If yes, and if there's a reasonable way to solve this problem, what would be the solution?
There is nothing saying that the subgraph has to be connected. So any subgraph of $K_{7,9}$ with all of its vertices and sixteen edges would qualify.
Counting the number of connected subgraphs with 16 vertices and 16 edges would be considerably harder. The easy part is that $K_{m,n}$ has $m^{n-1}n^{m-1}$ spanning trees, so that comes out to $7^8\cdot9^6$ subgraphs with 16 vertices and 15 edges. (That result is easy to state but not so easy to prove IIRC.) But adding an extra edge of the $63-15$ remaining to that isn't so easy because that will create a cycle and there will be as many trees that could form that graph as there are edges in that particular cycle. I don't want to think about that any more.