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.

  • 1
    $\begingroup$ It's at least $2^{(n-1)(m-1)}$, If this is enough for you to see is very big. $\endgroup$ – user742 Jul 11 '13 at 17:29
  • $\begingroup$ I know that it is very big. But how big? $\endgroup$ – Unapiedra Jul 11 '13 at 17:32
  • 1
    $\begingroup$ I think in this big range $2^{(m-1)(n-1)}$ is somehow precise, but you looking for the exact number? Can I ask you what's your original problem? $\endgroup$ – user742 Jul 11 '13 at 17:33
  • $\begingroup$ Yes, I am trying to solve Project Euler 434. I know that a grid truss is rigid if the bipartite graph formed from it, is connected. Form the bipartite graph by having U being all rows and V being all columns, add an edge for every diagonal member in (row, col). iust.ac.ir/files/cefsse/pg.cef/Contents/chapter_3.pdf , page 98 $\endgroup$ – Unapiedra Jul 11 '13 at 18:16

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.


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

| cite | improve this answer | |
  • $\begingroup$ This is hard problem, otherwise someone here or in SO would provide a complete answer. But point of my comment was if you want to brute force on something like this, you should not do it. $\endgroup$ – user742 Jul 18 '13 at 12:37
  • $\begingroup$ And you don't have to, because the Tutte polynomial gives you the answer! Also I never wanted to run anything on the set of combinations, I just wanted to know the size. Calculating this is far from brute force. One implementation I found gives me this for n=100, m=100 in about a second. $\endgroup$ – Unapiedra Jul 18 '13 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.