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)$.