I got a really hard problem that is there any graphs G(G is not a self-complementary graph) that has the same count of spanning tree with its complement tree G'?
I tried multiple methods to get the result but got nothing.
I tried to use Java to generate all graphs and get its complement graph and compare their counts of spanning trees. It is aged so that I stopped it when generating order-10 graphs. That is, now I know it doesn't exist with graphs that have less than 10 vertices. I tried to use the degree matrix of G to show if there can or cannot be the same co-factor with a graphic matrix with its complement graph's matrix, but as the calculate was based on the matrixes, I didn't get a reasonable result that can prove anything. Thus, are there any graphs that have the same count of spanning tree with its complement graph and why?
Thanks!
There are such graphs. Indeed, there are infinitely many non self-complementary graphs that have the same Tutte polynomial as their complement; see this mathoverflow post. Since the Tutte polynomial encodes the number of spanning forests of a graph (i.e. if $T_G$ is the Tutte polynomial of $G$, $T_G(1,1)$ is the number of spanning forests), this answers your question affirmatively.
Well, except you were asking about spanning trees and I'm talking about spanning forests. But at a cursory glance it seems that the construction cited in the link gives connected graphs with connected complements, in which case the two notions are the same.