Wo consider the graph $G$ that we get by deleting any edge from the complete bipartite graph $K_{7,8}$. How many spanning trees does the complement graph $\overline{G}$ of $G$ have?
I have thought the following:
The graph $K_{7,8}$ has $7^{8-1} \cdot 8^{7-1}$ spanning trees.
Then $G$ has $6^{7-1} \cdot 7^{6-1}$ spanning trees.
Does $\overline{G}$ have $7^{8-1} \cdot 8^{7-1}-6^{7-1} \cdot 7^{6-1}$ spanning trees. But, the result that we get isn't a possible one. So is my idea wrong?
Are you sure that $G$ has $6^{7-1} \cdot 7^{6-1}$ spanning trees? $G$ doesn't become a $K_{6,7}$ after deleting one of the edges, so you can't use that formula. To find the number of spanning trees on $G$ you need to find the number of spanning trees of $K_{7,8}$ using the deleted edges and subtract that from the total number of spanning trees of $K_{7,8}$.
To calculate the latter you can use the symmetry of $K_{7,8}$ and realize that deletion of any edges will result in removing the same amound of spanning trees. So now we have $7\cdot8 = 56$ edges and each spanning three contains $7+8-1=14$ edges and hence each edge is contained in $\frac{8^{6}\cdot 7^{7}}{7\cdot 8} \cdot 14=2\cdot8^5\cdot7^7$ spanning tree. Hence $G$ has $8^{6}\cdot 7^{7} - 2\cdot8^5\cdot7^7 = 4\cdot8^5\cdot7^7$ spanning trees.
On the other side $\overline{G}$ can't be calculated as a difference between the spanning trees of $K_{7,8}$ and the spanning trees of $G$. Nevertheless if you draw $\overline{G}$ you will see it consists of two complete graphs $K_7$ and $K_8$ connected by an edge. Hence total number of spanning trees of $\overline{G}$ is $8^6\cdot 7^5$