[Solved]: Number of Combinations of Connected Bipartite Graphs

Problem Detail: 

Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?

Obviously there are $2^{n m}$ different set of edges but many will be disconnected.

Asked By : Unapiedra

Answered By : Unapiedra

The answer is was given by David Eisenstadt in his answer to my question.

The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).

While I don't fully understand everything about this problem, the intuitive reasoning is as follows:

Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.

Note:

If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13229