In an undirected bipartite graph, there are two disjoint sets, S1 and S2, such that every edge connects a node in S1 to one in S2. This undirected bipartite graph also satisfies further requirement as follows:

1) There are N1 nodes in S1, and N2 nodes in S2.

2) The maximum degree of each node is 1. In another word, each node has at most 1 link.

3) There are K links totally in the bipartite graph. Obviously, K<=min(N1,N2)

[Question] How many such undirected bipartite graphs exist ?


Let $N2$=M is minimum and $N1$ is N. Let the number of subset of M of length i is $M_i$ I think the answer to your question is.

$\left[\displaystyle\sum\limits_{i=1}^n C(M,i)*P(N,i)\right] + 1$.

Explanation is. If the number of non-isolated vertices in $M$ is $i$ we can choose such subset in $C(M,i)$ ways. And for each of them we can choose their neighbors in $P(N,i)$ ways. Here $C(M,i)$ means number of combination from $M$ objects of size $i$ and $P(N,i)$ means number of permutations from $N$ objects of size $i$.

Edit: The above answer give a general result i.e when k is not fixed. But as far as the question is concerned it does not give the exact answer.

So when $k$ is fixed we have the number of such graphs as: $C(M,K)*P(N,K)$.

  • $\begingroup$ I think your solution is wrong, because you did not use the information in the requirement 3. Obviously, K should be included in the final solution. $\endgroup$
    – Chaos Mage
    Feb 12 '14 at 9:07
  • $\begingroup$ I guess your $P(N,i)$ means the number of permutation of a N-size set with i elements. $\endgroup$
    – Chaos Mage
    Feb 13 '14 at 14:33
  • $\begingroup$ Yes,you are right. $\endgroup$
    – Dib
    Feb 13 '14 at 14: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.