# Number of Combinations of Connected Bipartite Graphs

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.

• It's at least $2^{(n-1)(m-1)}$, If this is enough for you to see is very big.
– user742
Jul 11, 2013 at 17:29
• I know that it is very big. But how big? Jul 11, 2013 at 17:32
• 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?
– user742
Jul 11, 2013 at 17:33
• 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 Jul 11, 2013 at 18:16

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