# 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 '13 at 17:29
• I know that it is very big. But how big? – Unapiedra Jul 11 '13 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 '13 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 – Unapiedra Jul 11 '13 at 18:16